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.
On Sun, Sep 11, 2016, 12:15 PM Mark Dickinson <dicki...@gmail.com> wrote: > > I am interested in making a non-trivial improvement to list.sort() [...] > > Would your proposed new sorting algorithm be stable? The language > currently guarantees stability for `list.sort` and `sorted`. > > -- > Mark >
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
