DOC: Clarify stability of sorting in documentation of DataFrame.sort_values for multiple columns / labels

[jotasi]

Location of the documentation

Description of the argument kind in the documentation of pandas.DataFrame.sort_values.

Documentation problem

The current documentation states (emphasize mine):

Choice of sorting algorithm. See also ndarray.np.sort for more information. mergesort is the only stable algorithm. For DataFrames, this option is only applied when sorting on a single column or label.

To me that means, that the kind argument is ignored if you sort by multiple columns / labels. But I think one could even interpret it as mergesort explicitely is not done in that case. Running some tests, it does look like the sorting is stable when sorting multiple columns / labels. But it is not written anywhere. If it really is guaranteed that the sorting is stable for sorting by multiple columns / labels, it would be nice to have this written down explicitely in the documentation.

Suggested fix for documentation

IF that is actually the case, I would suggest to add a sentence to the effect that the sorting is stable if sorting is done by multiple columns / labels. E.g. change the kind argument description to:

Choice of sorting algorithm. See also ndarray.np.sort for more information. mergesort is the only stable algorithm. For DataFrames, this option is only applied when sorting on a single column or label. For DataFrames, if sorting by multiple columns or labels, this argument is ignored, defaulting to a stable sorting algorithm.

[arw2019]

Are you interested in submitting a PR?

[jotasi]

Sure, I can do that. So the stability of sorting for multiple columns or labels is guaranteed?

[arw2019]

I'm not that familiar with that part of the codebase but merge sort, as stated, is definitely stable. We also appear to have an implementation of counting sort for multi-key sorting which is stable:

pandas/pandas/core/sorting.py

Lines 566 to 579 in 32bebdb

	def get_group_index_sorter(group_index, ngroups: int):
	"""
	algos.groupsort_indexer implements `counting sort` and it is at least
	O(ngroups), where
	ngroups = prod(shape)
	shape = map(len, keys)
	that is, linear in the number of combinations (cartesian product) of unique
	values of groupby keys. This can be huge when doing multi-key groupby.
	np.argsort(kind='mergesort') is O(count x log(count)) where count is the
	length of the data-frame;
	Both algorithms are `stable` sort and that is necessary for correctness of
	groupby operations. e.g. consider:
	df.groupby(key)[col].transform('first')
	"""

If we're using quicksort I'm not sure (can be stable/unstable and I don't know which one(s?) we have)

[jotasi]

Ok. Thanks for the help. I'll have a closer look at the code base trying to understand what is done for multiple columns / labels and then open a PR. I'll definitely not get to that before the weekend though.