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

<p>For example, If I call <code>argsort([0,0,1])</code>, will it return:</p>

<ul>
<li><p><code>[0,1,2]</code>?</p></li>
<li><p><code>[1,0,2]</code>?</p></li>
<li><p>it depends?</p></li>
</ul>

<p>This is documented for the <a href="http://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html#numpy.sort" rel="nofollow"><code>numpy.sort()</code> function</a> (linked from the <a href="http://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html" rel="nofollow"><code>numpy.argsort()</code> page</a>).</p>

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

<pre><code>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
</code></pre>

<p>For your <em>specific</em> example, quicksort returns <code>[0, 1, 2]</code>, as does mergesort. Heapsort returns <code>[1, 0, 2]</code> instead:</p>

<pre><code>&gt;&gt;&gt; from numpy import argsort
&gt;&gt;&gt; argsort([0,0,1])
array([0, 1, 2])
&gt;&gt;&gt; argsort([0,0,1], kind='mergesort')
array([0, 1, 2])
&gt;&gt;&gt; argsort([0,0,1], kind='heapsort')
array([1, 0, 2])
</code></pre>

<p>However, given the <em>same input</em>, each sort algorithm will produce the <em>same output</em> again. You won't randomly see <code>1</code> and <code>0</code> 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.</p>

<p>Also see the <a href="https://en.wikipedia.org/wiki/Sorting_algorithm#Stability" rel="nofollow"><em>stability</em> section</a> of the Wikipedia article on sorting algorithms.</p>

python sorting numpy