CLN: handle EAs and fast path (no bounds checking) in safe_sort
State: closed

This is a possible alternative solution to what we have been discussing in https://github.com/pandas-dev/pandas/pull/25592.

This moves the logic into `safe_sort`, with:

- adding a `check_outofbounds` keyword to disable extra checks (otherwise the performance benefit of `take_1d` is lost)
- fixing `safe_sort` to work for EAs

The `check_outofbounds` make it a bit more complicated, but without it, we can't benefit of the performance improvement for which `take_1d` was used originally in `factorize`.

(another solution is to simply decide that this performance improvement is not worth this extra code, and we simply use the current `safe_sort` (but fixed to work for EAs) in `factorize`)

Need to add some more tests for the combination of EAs with a custom na_sentinel (a case that is currently broken)

Labels:
name: Algos
description: Non-arithmetic algos: value_counts, factorize, sorting, isin, clip, shift, diff
name: ExtensionArray
description: Extending pandas with custom dtypes or arrays.

Comments:
Hello @jorisvandenbossche! 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-05-06 18:52:38 UTC
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25696?src=pr&el=h1) Report
> Merging [#25696](https://codecov.io/gh/pandas-dev/pandas/pull/25696?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/a8fad16899bedfc3dabb6f196217d0c1004b231a?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `100%`.

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

```diff
@@            Coverage Diff             @@
##           master   #25696      +/-   ##
==========================================
+ Coverage   91.28%   91.28%   +<.01%     
==========================================
  Files         173      173              
  Lines       52967    52969       +2     
==========================================
+ Hits        48351    48353       +2     
  Misses       4616     4616
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `89.86% <100%> (ø)` | :arrow_up: |
| #single | `41.74% <57.89%> (+0.01%)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/25696?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/sorting.py](https://codecov.io/gh/pandas-dev/pandas/pull/25696/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc29ydGluZy5weQ==) | `98.36% <100%> (+0.06%)` | :arrow_up: |
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/25696/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.72% <100%> (-0.07%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25696?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/25696?src=pr&el=footer). Last update [a8fad16...c6203cb](https://codecov.io/gh/pandas-dev/pandas/pull/25696?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/25696?src=pr&el=h1) Report
> Merging [#25696](https://codecov.io/gh/pandas-dev/pandas/pull/25696?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/71207255f32af73cd701fe4ecf56a643c925a9e1?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/25696/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/25696?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #25696      +/-   ##
==========================================
- Coverage   91.98%   91.98%   -0.01%     
==========================================
  Files         175      175              
  Lines       52374    52375       +1     
==========================================
- Hits        48178    48175       -3     
- Misses       4196     4200       +4
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.53% <100%> (ø)` | :arrow_up: |
| #single | `40.75% <55.55%> (-0.12%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/25696?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/sorting.py](https://codecov.io/gh/pandas-dev/pandas/pull/25696/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc29ydGluZy5weQ==) | `98.35% <100%> (+0.06%)` | :arrow_up: |
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/25696/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.73% <100%> (-0.07%)` | :arrow_down: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/25696/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/25696/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `96.9% <0%> (-0.12%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25696?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/25696?src=pr&el=footer). Last update [7120725...151aa6a](https://codecov.io/gh/pandas-dev/pandas/pull/25696?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

Coming back to this

> would rather just fix take_1d

For `take_1d` itself, I am not sure it makes a lot of sense to support this. Currently, it is by definition that -1 values in the `indexer` passed to take signal missing values. The only use case for having this configurable would be this one, while it complicates the interface throughout pandas (eg also EAs would need to support this, as `take_1d` dispatch to them)
can you merge master
@jreback conflicts resolved, if you can take another look
thanks @jorisvandenbossche nice cleanup & tests.