DOC: Clarify that DataFrame.sort_values is stable for sorting by multiple columns or labels
State: closed

- [x] closes #38357
- ~~tests added / passed~~
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- ~~whatsnew entry~~

From what I understand from the code, for `by` containing more than one entry, `pandas.DataFrame.sort_values` uses `pandas.core.sorting.lexsort_indexer`, which converts the columns to ordered `Categorical`s, gets grouped lexicographic group indices via `get_group_index`, compressed these via `compress_group_index` and then sorts using counting sort or mergesort via `get_group_index_sorter`. Both of these are stable, as explained in `get_group_index_sorter`'s docstring. Therefore, the sorting should be stable if `sort_values` is called with `len(by)>1`.

Labels:
name: Docs
name: Reshaping
description: Concat, Merge/Join, Stack/Unstack, Explode

Comments:
Hello @jotasi! Thanks for updating this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:





There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers: 

##### Comment last updated at 2020-12-22 18:13:05 UTC
Good point!

There is a test that verifies that the counting sort is stable by comparing it to numpy's `argsort` with `kind="mergesort"`, which is stable:

https://github.com/pandas-dev/pandas/blob/e2dec8d03020eb2b31d376a7fcd7348977c6a319/pandas/tests/test_algos.py#L2118-L2138

The mergesort in `get_group_index_sorter` is done by `argsort` with `kind="mergesort"`.

There is also a test case that tests the `lexsort_indexer`, which tests that the `None` entries are sorted stably (no other duplicates are in the data though):

https://github.com/pandas-dev/pandas/blob/e2dec8d03020eb2b31d376a7fcd7348977c6a319/pandas/tests/test_sorting.py#L104-L124

If you think it's worthwhile, I can also add a test case verifying that the multicolumn sort is stable directly. (I at least have not found any such test.) 
> Good point!
> 
> There is a test that verifies that the counting sort is stable by comparing it to numpy's `argsort` with `kind="mergesort"`, which is stable:
> 
> https://github.com/pandas-dev/pandas/blob/e2dec8d03020eb2b31d376a7fcd7348977c6a319/pandas/tests/test_algos.py#L2118-L2138
> 
> The mergesort in `get_group_index_sorter` is done by `argsort` with `kind="mergesort"`.
> 
> There is also a test case that tests the `lexsort_indexer`, which tests that the `None` entries are sorted stably (no other duplicates are in the data though):
> 
> https://github.com/pandas-dev/pandas/blob/e2dec8d03020eb2b31d376a7fcd7348977c6a319/pandas/tests/test_sorting.py#L104-L124
> 
> If you think it's worthwhile, I can also add a test case verifying that the multicolumn sort is stable directly. (I at least have not found any such test.)

Thanks for looking into this! I think that's worth doing though not in this PR (it's always good to keep orthogonal tasks separate)
@jotasi can you add  test for the multi-column sorting as well.
@jreback Sure I can do that. There is already a test that according to its name should test this but doesn't really as it doesn't contain duplicated pairs:

https://github.com/pandas-dev/pandas/blob/4b7c4bb5d65806a74b6b5e616433928918cca455/pandas/tests/frame/methods/test_sort_values.py#L220-L241

I'll just adapt that one.

Should I open a new PR as @arw2019 suggested or should I do it here?
@jotasi happy in this PR
@jreback Thanks. The checks are done now. The Travis build is failing. But it looks like this is unrelated to the changes here.
thanks @jotasi very nice, keep em coming!