API: ExtensionArray.argsort places the missing value at the end 
State: closed

-  closes #21801
-  tests added
-  passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
-  whatsnew entry

`_values_for_argsort` returns different values for missing value in different EA. For example, missing value in `PandasArray` gets `np.nan` and in `PeriodArray` gets  `-9223372036854775808` (in my machine). `np.argsort` places `np.nan` at the end and the negative number in the beginning.

In this PR, `ExtensionArray.argsort` separates the array into two parts, data and missing values. Sort the data part and finally append missing part to it. The approach can work in general, no matter what the replacement of missing value in `values_for_argsort` is.

Labels:
name: API Design
name: ExtensionArray
description: Extending pandas with custom dtypes or arrays.

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=h1) Report
> Merging [#26354](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/2d2606d8541ecf114b8708d9e6e8f9a1af7ee115?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/26354/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #26354      +/-   ##
==========================================
- Coverage   91.86%   91.85%   -0.01%     
==========================================
  Files         179      179              
  Lines       50700    50701       +1     
==========================================
- Hits        46576    46573       -3     
- Misses       4124     4128       +4
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.45% <100%> (ø)` | :arrow_up: |
| #single | `41.12% <53.33%> (-0.06%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/arrays/integer.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2ludGVnZXIucHk=) | `96.25% <ø> (-0.06%)` | :arrow_down: |
| [pandas/core/arrays/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2Jhc2UucHk=) | `98.87% <100%> (-0.01%)` | :arrow_down: |
| [pandas/core/arrays/period.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL3BlcmlvZC5weQ==) | `98.3% <100%> (ø)` | :arrow_up: |
| [pandas/core/arrays/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2NhdGVnb3JpY2FsLnB5) | `95.82% <100%> (+0.02%)` | :arrow_up: |
| [pandas/core/sorting.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc29ydGluZy5weQ==) | `98.36% <100%> (ø)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `88.88% <0%> (-11.12%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `96.88% <0%> (-0.12%)` | :arrow_down: |
| [pandas/core/arrays/sparse.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL3NwYXJzZS5weQ==) | `93.59% <0%> (ø)` | :arrow_up: |
| [pandas/core/arrays/numpy\_.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL251bXB5Xy5weQ==) | `94.49% <0%> (ø)` | :arrow_up: |
| [pandas/core/arrays/timedeltas.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL3RpbWVkZWx0YXMucHk=) | `88.82% <0%> (ø)` | :arrow_up: |
| ... and [3 more](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=footer). Last update [2d2606d...84f87a8](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=h1) Report
> Merging [#26354](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/bb0376c209d97e49b9c94038926ee62ddc0ee84d?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/26354/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #26354      +/-   ##
==========================================
- Coverage   92.04%   92.03%   -0.01%     
==========================================
  Files         175      175              
  Lines       52292    52308      +16     
==========================================
+ Hits        48133    48144      +11     
- Misses       4159     4164       +5
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.59% <100%> (ø)` | :arrow_up: |
| #single | `40.7% <26.66%> (-0.18%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/arrays/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2Jhc2UucHk=) | `99.48% <100%> (+0.04%)` | :arrow_up: |
| [pandas/core/arrays/datetimelike.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2RhdGV0aW1lbGlrZS5weQ==) | `97.71% <100%> (ø)` | :arrow_up: |
| [pandas/core/arrays/period.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL3BlcmlvZC5weQ==) | `98.53% <100%> (ø)` | :arrow_up: |
| [pandas/core/arrays/integer.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2ludGVnZXIucHk=) | `96.36% <100%> (+0.01%)` | :arrow_up: |
| [pandas/core/arrays/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2NhdGVnb3JpY2FsLnB5) | `95.95% <100%> (ø)` | :arrow_up: |
| [pandas/core/sorting.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc29ydGluZy5weQ==) | `98.35% <100%> (ø)` | :arrow_up: |
| [pandas/core/arrays/numpy\_.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL251bXB5Xy5weQ==) | `94.49% <100%> (ø)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `78.94% <0%> (-10.53%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.01% <0%> (-0.12%)` | :arrow_down: |
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/26354/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `90.6% <0%> (-0.11%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=footer). Last update [bb0376c...73f88a5](https://codecov.io/gh/pandas-dev/pandas/pull/26354?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

@TomAugspurger do you have anything else to implement?
Looks like Jeff had some. 

> On May 23, 2019, at 22:05, Mak Sze Chun <notifications@github.com> wrote:
> 
> @TomAugspurger do you have anything else to implement?
> 
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub, or mute the thread.

1. @jorisvandenbossche The case of `Categorical` will be handled in a separate PR. As you said, the 'NA first' behaviour is required in the test `test_sort_values_na_position` and `test_sort_index_na_position_with_categories`.

2. `sorting.nargsort` calls `__array__` of EAs which has a similar output as `_values_for_argsort`. So some `_values_for_argsort` methods are removed.
https://github.com/pandas-dev/pandas/blob/891a419a5155e6b42c0696a81cf853b6f3febbf7/pandas/core/sorting.py#L264
can you add some tests to assert the results of the sort
@makbigc can you also add any tests that are in https://github.com/pandas-dev/pandas/pull/25595 as well (this PR will supersed)
Hello @makbigc! 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 2019-06-14 08:10:10 UTC
The test_nargsort_datetimearray_warning was already added in #25629.
Another test_nargsort_extension_array is added. 
Jeff. The `nargsort` is the wrapper of `np.argsort`. `argsort` of EAs has been using `np.argsort`. The replacement of `argsort` with `nargsort` doesn't improve the performance. This PR only standardizes the position of NA values after sorting.
It is better to pass EA directly to `nargsort`. If the output of `EA._values_for_argsort` is passed to `nargsort`, the information of NA values' location may be lost in `nargsort`. 

For example, `PeriodArray` is passed directly to `nargsort`. The location of its NA values can be obtained by calling `isna()`. After calling `_values_for_argsort` and passing the output `np.ndarray` to `nargsort`, the NA values are replaced with negative number. `nargsort` can no longer retrieve the location of NA values.

The `nargsort` has been modified in #26854. So the `_values_for_argsort` is called there after the retrieval of location of NA values (i.e. calling `isna()`). Besides, no matter what the replacement value for NA in `_values_for_argsort`, `nargsort` can still function properly.
@makbigc can you merge master
After #26854, it is better to pass EA directly to `nargsort`, because the information about the positions of NaN values can be preserved. Then `nargsort` calls `EA._values_for_argsort` itself. This PR is continued in #27137 in which the change of code is smaller.