DEPR: DataFrame.value_counts(sort=False) sorts

[rhshadrach]

I noticed this oddity while working on #55951. There is a subtle difference in the docstrings for the sort argument:

DataFrame.value_counts:

Sort by frequencies when True. Sort by DataFrame column values when False.

DataFrameGroupBy.value_counts:

Sort by frequencies.

It seems surprising to me that DataFrame.value_counts(sort=False) still sorts:

df = pd.DataFrame({'a': [2, 1, 1], 0: [3, 4, 3]})
print(df)
#    a  0
# 0  2  3
# 1  1  4
# 2  1  3

print(df.value_counts(sort=False))
# a  0
# 1  3    1
#    4    1
# 2  3    1

whereas my expected result would be to keep the same order as the input.

print(df.value_counts(sort=False))
# a  0
# 2  3    1
# 1  4    1
# 1  3    1

I propose we deprecate this behavior and not sort at all when sort=False.