Numpy argsort instability

Question

Lately, I have been experimenting np.argsort and I have realized something weird.

If you run the following code, you will get the result:

In [0]: np.argsort([3]*16)
Out[0]:
array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
      dtype=int64)

But if you make just a little change:

In [1]: np.argsort([3]*17)
Out[1]:
array([ 0, 14, 13, 12, 11, 10,  9, 15,  8,  6,  5,  4,  3,  2,  1,  7, 16],
      dtype=int64)

I know the default method for numpy argsort is quicksort, which is an unstable sorting algorithm. But, there is an reasonably explanation about the differents behavior above? Is this related to quicksort's choice of pivot? If so, why?

Answer 1

I may be wrong as I didn't look into it too deeply but it seems numpy uses a introsort kind of hybrid algorithm resorting to insertion sort (which is stable) for small ranges.

Guess looking at the code should give you a better insight. Look at the different paths the code can follow, SMALL_QUICKSORT should be the magic number you're looking for.