Numpy argsort处理相同元素数组的排序不稳定性疑问

Great question! This behavior boils down to how NumPy's default argsort algorithm handles small vs. large arrays, combined with the stability of the sorting algorithms involved. Let's break it down step by step:

1. NumPy's default sorting switch: Quicksort vs. Insertion Sort #

NumPy's argsort uses quicksort by default, but it has a built-in optimization: for small arrays (specifically, arrays with length ≤ 16, a hardcoded threshold in NumPy's implementation), it switches to insertion sort instead.

• Insertion sort is a stable sorting algorithm: when elements have equal values, it preserves their original relative order. That's why np.argsort([3]*16) returns indices in perfect sequential order—all elements are equal, so insertion sort just keeps the original index positions intact.
• Quicksort is an unstable sorting algorithm: it doesn't guarantee that equal elements retain their original relative order. For arrays longer than 16 (like your 17-element array), NumPy uses quicksort, which explains the jumbled index output.

2. What happens with quicksort when all elements are equal? #

When every element in the array is identical, quicksort's partitioning step still runs:

• It picks a pivot element (NumPy's implementation uses a median-of-three approach for pivot choice).
• Since all elements equal the pivot, the partitioning splits the array into segments of equal elements. The recursive sorting of these segments rearranges indices in non-sequential order, because quicksort doesn't track original positions for equal values.

The jumbled output you see for the 17-element array is just a side effect of quicksort's internal partitioning and recursion steps when dealing with all-equal values—there's no intentional "logic" to the order beyond how the algorithm happens to rearrange indices during its unstable sort process.

To confirm this behavior #

If you force argsort to use a stable algorithm like mergesort, you'll get sequential indices for both array lengths:

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

内容的提问来源于stack exchange，提问作者Arnaldo Gualberto