BUG: stabilize sort_values algorithms for Series and time-like Indices
State: closed

- [X] closes #35922
- [X] 18 tests changed / 18 passed
- [X] passes `black pandas`
- [X] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [X] whatsnew entry

## Problem

Our `sort_values` functions currently behave differently for different objects: for most `Index` subclasses they are stable when sorting in descending order (this was introduced by #35604), but for DateTime-like `Index` subclasses and `Series` they are unstable. This isn't good as sorting should be stable across the board.

## Details

Came across this one while introducing missing-value support to `Index.sort_values` in #35604, so I had to limit that PR to non-DateTime-like `Index` subclasses. The problem was that we had different expectations for sorting stability baked into our test suite, so unifying sorting algorithms and missing-value support needed a bunch of careful test changes and altering both `sort_values` and algorithms in `sorting.py`.

Since this PR necessarily includes changes in several places, I have commented on all the changes made in the code and the unusual changes in the tests to make reviewing the code easier (see "On test changes" below).

## On test changes

Most changes I made in the tests are for cases where we were expecting an unstable sort or expected NaNs to be sorted to the beginning of a list of duplicates for ascending sort and to the end for descending (we forced this by inserting NaN-likes at 0 position and reversing when sorting in descending order in `Series.sort_values`).

## Default behavior changes

Since DateTime-like `Index` subclasses now support `na_position` using the same implementation as the other `Index` subclasses, they now sort missing values to the end of the `Index` by default.

## Performance

Ran the full benchmark suite, and there are no performance regressions.

## Out-of-scope

The only type I didn't touch so far is MultiIndex. It can't be sorted the same way through nargsort, and I don't think we should be doing it in this PR, if it all (stabilizing descending order MultiIndex.sort_values will definitely be a PITA, and it's a very narrow use case, in my opinion).

Labels:
name: Bug
name: Algos
description: Non-arithmetic algos: value_counts, factorize, sorting, isin, clip, shift, diff

Comments:
Hello @AlexKirko! 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-10-31 04:50:22 UTC
Stabilized the sorts, now looking for good ways to deal with 134 failing tests. Will likely take me a couple more days. Some tests have to be altered, but I'd like to change as few tests as necessary to get this done.
@jreback 
This is ready for review, I think. Just finished running the benchmark suite, and everything is fine.
I'm not clear on what "stability" means in this context.  In #35922 you wrote

```
ind = pd.Index([1, 1, 2, 3])

>>> ind.sort_values(ascending=False, return_indexer=True)[1]
array([3, 2, 1, 0], dtype=int64)   # <-- old behavior
array([3, 2, 0, 1], dtype=int64)   # <-- new/expected behavior
```

Is it obvious why the latter is preferred?


> I'm not clear on what "stability" means in this context. In #35922 you wrote
> 
> ```
> ind = pd.Index([1, 1, 2, 3])
> 
> >>> ind.sort_values(ascending=False, return_indexer=True)[1]
> array([3, 2, 1, 0], dtype=int64)   # <-- old behavior
> array([3, 2, 0, 1], dtype=int64)   # <-- new/expected behavior
> ```
> 
> Is it obvious why the latter is preferred?

@jbrockmendel I think it's best to consider something like this right now on master:

```python
s = pd.Series(["A", "AA", "BB", "CAC"], dtype="object")
s.sort_values(ascending=False, key=lambda ser: ser.str.len())

OUT:
3    CAC
2     BB
1     AA
0      A
dtype: object
```
I don't think that swapping is expected here.

Then consider that you might be sorting a DataFrame with several columns, and a column with duplicates might be the first one. In this case you likely wouldn't expect a descending sort to change duplicate order. Or you could be using something like `nlargest` and get weirdness because there is a descending sort in there and it swaps elements.

Obviously, we could get by with a convention that we always revert duplicate order with a descending sort by being careful, but I believe keeping duplicate order is cleaner. In cases where it doesn't matter, it's the same, and when it does matter (as in `nlargest` and the like), you don't need to remember that you need extra reversals.
Not sure what's going on with the Window py37_np16 fail. Doesn't look like it has anything to do with this PR. It's `test_binary_arith_ops` in `computation/test_eval`.
makes sense, thanks for spelling it out for me
test_binary_arith_ops has been mucking up all the builds for a little while now; you can ignore it here
@jreback 
I think this is ready for another look.

1. No longer process missing values separately in `Series.sort_values`, just pass everything to `ensure_key_mapping`.
2. Since we now pass the `Series` instead of the underlying array, we can now safely cast in `ensure_key_mapping`.
3. Clean up legacy try / except in nargsort (doesn't affect test suite, plus tested manually).
4. Answer @jbrockmendel 's question and add the answer to the issue for future reference.
5. Rewrite and expand whatsnew, create "Other API changes" section in whatsnew (under Enhancements), and put it there.

More detailed answers to your comments in replies above.

The test fails on Win py38 and on 32-bit are happening for many PRs and have nothing to do with this one (Win 38 fails are going through troubleshooting in #37455, 32-bit fails are examined in #37473)


Update: Web and Docs shouldn't be complaining, probably missed something. Checking them out.
 Had forgotten a colon. Fixed it.
@jreback 
Most of the unrelated stuff has been fixed and merged. The Windows py38_np18 pipeline still fails, but that's unrelated and being examined in #37455 by @jbrockmendel 
@jreback 
Made the change, all green-ish.
thanks @AlexKirko very nice!