BUG/PERF: SeriesGroupBy.value_counts sorting bug and categorical performance
State: closed

- [x] closes #50482 (Replace xxxx with the GitHub issue number)
- [x] closes #46202
- [x] [Tests added and passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#writing-tests) if fixing a bug or adding a new feature
- [x] All [code checks passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit).
- [x] Added [type annotations](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#type-hints) to new arguments/methods/functions.
- [x] Added an entry in the latest `doc/source/whatsnew/vX.X.X.rst` file if fixing a bug or adding a new feature.

This takes a bit of a perf hit with SeriesGroupBy.value_counts; I think this is because the current implementation always sorts the groupers (which is also fixed here).

https://github.com/pandas-dev/pandas/blob/0a4ba64212bf440f37515b242e5746fea943c62d/pandas/core/groupby/generic.py#L711-L715

Also get a good perf improvement with categorical.

<details>
<summary>Perf code</summary>

```
import numpy as np
import pandas as pd
import time

size = 1000
col1_possible_values = ["".join(np.random.choice(list("ABCDEFGHIJKLMNOPRSTUVWXYZ"), 20)) for _ in range(700000)]
col2_possible_values = ["".join(np.random.choice(list("ABCDEFGHIJKLMNOPRSTUVWXYZ"), 10)) for _ in range(860)]
col1_values = np.random.choice(col1_possible_values, size=size, replace=True)
col2_values = np.random.choice(col2_possible_values, size=size, replace=True)
col3_values = np.random.choice(col2_possible_values, size=size, replace=True)
df = pd.DataFrame(zip(col1_values, col2_values, col3_values), columns=["col1", "col2", "col3"])

print('DataFrameGroupBy - object')
%timeit df.groupby("col1").value_counts()

print('SeriesGroupBy - object')
%timeit df.groupby("col1")["col2"].value_counts()

df['col2'] = df['col2'].astype('category')

print('DataFrameGroupBy - category')
%timeit df.groupby("col1", observed=True)[["col2"]].value_counts()

print('SeriesGroupBy - category')
%timeit df.groupby("col1", observed=True)["col2"].value_counts()
```

</details>

```
# main
DataFrameGroupBy - object
4.09 ms ± 97.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
SeriesGroupBy - object
1.32 ms ± 7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
DataFrameGroupBy - category
86.1 ms ± 611 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
SeriesGroupBy - category
654 ms ± 7.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# This PR
DataFrameGroupBy - object
4.1 ms ± 53.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
SeriesGroupBy - object
2 ms ± 17.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
DataFrameGroupBy - category
84.7 ms ± 576 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
SeriesGroupBy - category
83.1 ms ± 565 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

Labels:
name: Bug
name: Groupby
name: Performance
description: Memory or execution speed performance
name: Algos
description: Non-arithmetic algos: value_counts, factorize, sorting, isin, clip, shift, diff

Comments:
Merging to avoid any further whatsnew conflicts