Is Numpy's argsort deterministic?

Question

Let's say I have a bunch of objects to sort, some of them having the same sorting criteria. Can I be certain numpy.argsort() will yield the same return every time ?

For example, If I call argsort([0,0,1]), will it return:

• [0,1,2]?

• [1,0,2]?

• it depends?

Answer 1

This is documented for the numpy.sort() function (linked from the numpy.argsort() page).

Whether or not the sort is stable depends on the sort algorithm you picked. The default is to use quicksort, and quicksort is not a stable sort. If you must have a stable sort, use kind='mergesort' instead:

kind        speed   worst case  work space  stable
‘quicksort’ 1       O(n^2)      0           no
‘mergesort’ 2       O(n*log(n)) ~n/2        yes
‘heapsort’  3       O(n*log(n)) 0           no

For your specific example, quicksort returns [0, 1, 2], as does mergesort. Heapsort returns [1, 0, 2] instead:

>>> from numpy import argsort
>>> argsort([0,0,1])
array([0, 1, 2])
>>> argsort([0,0,1], kind='mergesort')
array([0, 1, 2])
>>> argsort([0,0,1], kind='heapsort')
array([1, 0, 2])

However, given the same input, each sort algorithm will produce the same output again. You won't randomly see 1 and 0 swapped between runs with a given algorithm, even if it is an unstable. Instability doesn't imply randomness, it just means that the input order for values with the same sort key could end up being swapped. When values are swapped is entirely deterministic.

Also see the stability section of the Wikipedia article on sorting algorithms.