Text of discuss.python.org › t › adding-unstable-sort-to-cpython › 22301 as Styx crawled it on Nov 19, 2026. The page may have changed since. Only its words are kept, without pictures or layout, and only the first part of a long page.

Open the live page

Adding unstable sort to cpython - Ideas - Discussions on Python.org

Adding unstable sort to cpython Ideas alonme (alm) December 30, 2022, 1:35pm 1 Pythons sorting functions use timsort which is a stable sort. For some use cases the “stability” feature is unneeded, in which case an unstable sort can be used. Unstable sorting algorithms can be faster - and hence are useful in some use cases ( see GitHub - orlp/pdqsort: Pattern-defeating quicksort. benchmarks for example) For example, rust has an unstable sort - which was proposed in the following RFC which i believe explains the need and possible solutions in a great way. https://rust-lang.github.io/rfcs/1884-unstable-sort.html 2 Likes `seqtools` (`alglib` / `seqlib`) ericvsmith (Eric V.

Smith) December 30, 2022, 2:07pm 2 It seems to me that this is a case for a package on PyPI. If it becomes super popular we can consider it for the stdlib. 2 Likes smontanaro (Skip Montanaro) December 30, 2022, 2:08pm 3 I’ll leave detailed explanations to @tim.one , but I don’t think Python’s list sorting was guaranteed to be stable at the time. That suggests that had an unstable sort been faster, that’s what timsort would have become.

Rosuav (Chris Angelico) December 30, 2022, 2:39pm 4 Hack on CPython and replace the sorting algorithm with a specific one that you want to recommend. Benchmark it. Unless it’s faster, there’s no proposal here. If it IS faster, then the next question is: how much faster is it? In order for an unstable sort to be valuable, it has to be worth the complexity of having two different ways to sort things - one that works all the time, and one that only works some of the time.

That’s going to need a LOT of speed difference, so there’s going to need to be some very good-looking numbers along with the proposal. alonme (alm) December 30, 2022, 2:59pm 5 @Rosuav Both work “all the time”, they just do different work. I agree that its only worth the hassle if the speed difference is a major one, However i have reasons to believe it will be like that, rust’s “stable” sort is using timsort , and they wrote about pdqsort being 45% faster (See RFC) Is there any benchmark for sorting that CPython uses?

Rosuav (Chris Angelico) December 30, 2022, 3:31pm 6 Well, no, because an unstable sort can’t be used when you need stability, but a stable sort can be used when stability isn’t necessary. So the sort method that lists already have can be used for ALL situations, but the one you’re proposing can only be used when stability doesn’t matter. So unless it’s sufficiently fast, there’s no point adding the complexity of a second sort method.

Check the pyperformance suite. I’m not sure if there’s anything specific to sorting, but if you build CPython twice, once with the existing algorithm and once with a different one, you should be able to get some decent comparative data. Without any real hard data to work with, I would say that the simplicity of knowing that things “just work” is incredibly helpful. For example, knowing that dictionaries remember their insertion order (without having to explicitly select an order-remembering dictionary) is extremely handy, since it means there’s no agonizing decision about whether it’s worth paying a performance cost for convenience.

Same goes for stable sorting. Working across languages and having to remember to warp an algorithm against one language’s lack of promise of something is a lot more hassle than “oh, this is 3% slower”, which doesn’t change the way you code at all. So… how good can you make this? pf_moore (Paul Moore) December 30, 2022, 5:18pm 7 The arguments in the Rust RFC seem to be mostly about the fact that unstable sorts allow no-allocation strategies, and the fact that an unstable sort can be used with no-std.

So pdqsort is more attractive in a systems programming context. That’s not to say that performance isn’t important, but so is stability (for some applications) and the trade-offs in Python are different. Let’s wait to see some real-world performance data before deciding. tjreedy (Terry Jan Reedy) December 30, 2022, 7:08pm 8 A major goal of timsort was to exploit non-random structure in data to be sorted. For performance, it exploits the fact that ‘worse’ O(N N) algorithms can be real-time faster than academically ‘better’ O(N logN) algorithms for small N.

Notice that O(N logN) algorithms run fast for large N by splitting the problem into multiple small N pieces that can eventually run faster with N N insert sort. It turned out that for mergesort stability was possible with little loss of performance. Tim Peters included in the repository the following, which explains the benchmarks used for comparisons with the previous sort and variations of what became timsort. The github.io blog post linked above says Q: How much faster can unstable sort be?

A: Sorting 10M 64-bit integers using pdqsort (an unstable sort implementation) is 45% faster than using slice::sort . Detailed benchmarks are here . The repository readme, also linked above, makes it clear that machine ints are a special case that can be sped up with special tricks that I understood to not be applicable to strings and structures (which would include Python’s boxed ints). I don’t know to what extent slice::sort is timsort, as ‘timsort’ is not mentioned among the sources of pdqsort.

If it were timsort, then the answer here: Q: Is slice::sort ever faster than pdqsort? A: Yes, there are a few cases where it is faster. For example, if the slice consists of several pre-sorted sequences concatenated one after another, then slice::sort will most probably be faster. Another case is when using costly comparison functions, e.g. when sorting strings. slice::sort optimizes the number of comparisons very well, while pdqsort optimizes for fewer writes to memory at expense of slightly larger number of comparisons.

But other than that, slice::sort should be generally slower than pdqsort. should consider all the cases where timsort excels. Notice that pdqsort is slower with ‘ costly comparison functions ’ including strings. I presume this would even include python ints. My guess is that pdqsort might be of more interest to the numpy people, for sorting arrays of machine numbers. (I don’t know what it does now.) 1 Like da-woods (Da Woods) December 30, 2022, 8:23pm 9 FWIW here’s a trivial Cython wrapping of the C++ standard library sort and stable_sort functions: # distutils: language=c++ from libcpp.algorithm cimport sort, stable_sort as stable_sort_ from libcpp cimport bool as cppbool from cpython.sequence cimport PySequence_Fast_ITEMS from cpython cimport PyObject cdef cppbool lt(lhs, rhs) noexcept: return lhs < rhs def stable_sort(o): l = list(o) cdef PyObject** items = PySequence_Fast_ITEMS(l) cdef Py_ssize_t length = len(l) stable_sort_(items, items+length, lt) return l def unstable_sort(o): l = list(o) cdef PyObject** items = PySequence_Fast_ITEMS(l) cdef Py_ssize_t length = len(l) sort(items, items+length, lt) return l It doesn’t handle exceptions from the comparison function correctly (although that wouldn’t be too hard to do if you took the comparison function out of Cython), or do custom key functions/reverse like the real “sorted” function does.

On my PC >>> x = [ random.random() for _ in range(10000) ] >>> print(timeit.timeit("sort2.stable_sort(x)", globals=globals(), number=1000)) 2.6741872249986045 >>> print(timeit.timeit("sort2.unstable_sort(x)", globals=globals(), number=1000)) 3.218431173998397 >>> print(timeit.timeit("sorted(x)", globals=globals(), number=1000)) 1.5250315239973133 So Python comfortably beats the C++ stable sort, which actually beats the C++ unstable sort(?).

So the conclusion is that Python is competitive and that unstable sort may not be faster. Obviously more time and effort could be spent on this, but it isn’t an obvious win using what should be a decent external implementation. 1 Like alonme (alm) December 30, 2022, 8:36pm 10 regarding the st

The rest of this page is on the live site.