<div dir="ltr">The sort can be made stable, but that requires the allocation of an equal-sized auxiliary array. To quote from the paper: "Both list-based and two-array sorts entail Θ(n) space overhead. That overhead shrinks to Θ(logn) in American flag sort, which, like quicksort, trades off stability for space efficiency." So there are two options: follow C++ in providing a stable and unstable sort, or just use stable radix sort at the cost of allocating a scratch array. I understand why the first approach is essentially impossible, since it could break code written under the assumption that list.sort() is stable. But I think that in Python, since the list just holds pointers to objects instead of objects themselves, being in-place isn't that important: we're missing the cache all the time anyway since our objects are stored all over the place in memory. So I suppose the thing to do is to benchmark stable radix sort against timsort and see if it's still worth it. Again, I really don't think the auxiliary array would make that much of a difference. Note that in timsort we also use an auxiliary array.</div><span>
</span><br><div class="gmail_quote"><div dir="ltr">On Sun, Sep 11, 2016, 12:15 PM Mark Dickinson <<a href="mailto:dickinsm@gmail.com" target="_blank">dickinsm@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">> I am interested in making a non-trivial improvement to list.sort() [...]<br>
<br>
Would your proposed new sorting algorithm be stable? The language<br>
currently guarantees stability for `list.sort` and `sorted`.<br>
<br>
--<br>
Mark<br>
</blockquote></div>