ENH: making value_counts stable/keeping original ordering
State: closed

closes #12679
closes #11227
- [x] tests added / passed
- [x] Ensure all linting tests pass, see [here](https://pandas.pydata.org/pandas-docs/dev/development/contributing.html#code-standards) for how to run them
- [x] whatsnew entry

The order of the returned keys for `value_counts` aren't arbitrary (i.e. depending on the used hash function) but are original ordering (when sorted this applies for the keys with the same number of values).


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

Comments:
There are still some issues that needs to be addressed/discussed:

  1. `mode` needs probably to reuse the same "stable" functionality. Right now there are differences between `value_count` and `mode` (see #39007). If these differences are not deliberate and just a bug/oversight - that would make the life a little bit easier.
  2. `value_count` has now a special postprocessing step for nans, ensuring that e.g. `pd.NA` and `np.nan` are handled as the same object (https://github.com/pandas-dev/pandas/blob/f9ce9d6dcc28cc408bcffab8cb4fdc865e51c02a/pandas/core/algorithms.py#L877-L881)  The downside of this approach is, that nans aren't in the "original order". Probably a better approach would be something like this:

```python
cpdef stable_value_count_object(ndarray[object] values, bint dropna, na_representant=np.nan):
    ...
    for i in range(n):
        val = values[i]
        if checknull(val):
            val = na_representant  # uses one representant for all null-objects
        if not checknull(val) or not dropna:
            k = kh_get_{{ttype}}(table, <PyObject*>val)
            ...
```
this would be slightly faster than the current approach, would work also for `mode` out of the box if reused without additional postprocessing, and nans would keep their "original" place.

3. non-object branch is no longer nogil (https://github.com/pandas-dev/pandas/pull/39009/commits/71edcca847c5fe126dec6155dbdccf9f5e322b39#diff-f4f1cb812ad02cac95da4070745323e8cf31dfbcc65da52744bb6721439210bbR123) Not sure it is a big issue. However, to improve it, probably Int64Vector & Co: https://github.com/pandas-dev/pandas/blob/f1d4026973bfb650be63cbe87443570aa01935dd/pandas/_libs/hashtable_class_helper.pxi.in#L197-L204 should be improved. Right now there are some issues (e.g. the whole  `external_view_exists`-business is very annoying. Better would be no longer hold the reference to the from `to_array` returned object, as it cannot be safely used anyway (it could be resized outside making `data` a dangling pointer)) which I would like not to address in this PR.
surprising asv_bench showed no changes when ran with:

```
asv continuous -f 1.05 upstream/master HEAD  -b series_methods -b period -b categoricals -b frame_methods
```
I went on with 2. from comment https://github.com/pandas-dev/pandas/pull/39009#issuecomment-755726116

I think 1. and 3. from this comment are better as separate PRs.
can you merge master.
https://dev.azure.com/pandas-dev/pandas/_build/results?buildId=52863&view=logs&j=acc1347f-8235-55b0-95c7-0e2189e61659&t=486f34f1-eda6-516a-fc5d-d8195128dacd i think you need to update this test (was added since you did this PR originally)
@jreback  Thanks, fixed now
@jreback green
thanks @realead