I think it's fair to say that pdqsort (pattern-defeating quicksort) is overall the best unstable sort and timsort is overall the best stable sort in 2017, at least if you're implementing one for a standard library.<p>The standard sort algorithm in Rust is timsort[1] (slice::sort), but soon we'll have pdqsort as well[2] (slice::sort_unstable), which shows great benchmark numbers.[3] Actually, I should mention that both implementations are not 100% equivalent to what is typically considered as timsort and pdqsort, but they're pretty close.<p>It is notable that Rust is the first programming language to adopt pdqsort, and I believe its adoption will only grow in the future.<p>Here's a fun fact: Typical quicksorts (and introsorts) in standard libraries spend most of the time doing literally nothing - just waiting for the next instruction because of failed branch prediction! If you manage to eliminate branch misprediction, you can easily make sorting twice as fast! At least that is the case if you're sorting items by an integer key, or a tuple of integers, or something primitive like that (i.e. when comparison is rather cheap).<p>Pdqsort efficiently eliminates branch mispredictions and brings some other improvements over introsort as well - for example, the complexity becomes O(nk) if the input array is of length n and consists of only k different values. Of course, worst-case complexity is always O(n log n).<p>Finally, last week I implemented parallel sorts for Rayon (Rust's data parallelism library) based on timsort and pdqsort[4].<p>Check out the links for more information and benchmarks. And before you start criticizing the benchmarks, please keep in mind that they're rather simplistic, so please take them with a grain of salt.<p>I'd be happy to elaborate further and answer any questions. :)<p>[1] <a href="https://github.com/rust-lang/rust/pull/38192" rel="nofollow">https://github.com/rust-lang/rust/pull/38192</a><p>[2] <a href="https://github.com/rust-lang/rust/issues/40585" rel="nofollow">https://github.com/rust-lang/rust/issues/40585</a><p>[3] <a href="https://github.com/rust-lang/rust/pull/40601" rel="nofollow">https://github.com/rust-lang/rust/pull/40601</a><p>[4] <a href="https://github.com/nikomatsakis/rayon/pull/379" rel="nofollow">https://github.com/nikomatsakis/rayon/pull/379</a>
Rust's stable sort is based on timsort (<a href="https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort" rel="nofollow">https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...</a>) and unstable sort is based on pattern-defeating quicksort (<a href="https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable" rel="nofollow">https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...</a>). The documentation says that 'It [unstable sorting] is generally faster than stable sorting, except in a few special cases, e.g. when the slice consists of several concatenated sorted sequences.'
I would love to see the benchmark results against Timsort, the Python sorting algorithm that also implements a bunch of pragmatic heuristics for pattern sorting. Timsort has a slight advantage over pdqsort in that Timsort is stable, whereas pdqsort is not.<p>I see that timsort.h is in the benchmark directory, so it seems odd to me that the README doesn't mention the benchmark results.
I always wondered if there would be a way to have quicksort run slower than O(n ln(n)).<p>Due to that possibility, when I code up a sort routine, I use heap sort. It is guaranteed O(n ln(n)) worst case and achieves the Gleason bound for sorting by comparing keys which means that on average and worst case, on the number of key comparisons, it is impossible to do better than heap sort's O(n ln(n)) forever.<p>For a stable sort, sure, just extend the sort keys with a sequence number, do the sort, and remove the key extensions.<p>Quicksort has good main memory locality of reference and a possibility of some use of multiple threads, and heap sort seems to have neither. But there is a version of heap sort modified for doing better on locality of reference when the array being sorted is really large.<p>But, if are not too concerned about memory space, then don't have to care about the sort routine being <i>in place</i>. In that case, get O(n ln(n)), a stable sort,
no problems with locality of reference, and ability to sort huge arrays with just the old merge sort.<p>I long suspected that much of the interest in in-place, O(n ln(n)), stable sorting was due to some unspoken but strong goal of finding some fundamental <i>conservation law</i> of a trade off of processor time and memory space. Well, that didn't really happen. But heap sort is darned clever; I like it.
Just because I was confused: this is by Orson Peters who first invented pdq. It's not brand new (as in yesterday), but is a very, very recent innovation (2016).
Question as a non low-level developer, and please forgive my ignorance:<p>How is it that we're essentially 50 years in to writing sorting algorithms, and we still find improvements? Shouldn't sorting items be a "solved" problem by now?
[Post-edit] I made several edits to the post below. First, to make an argument. Second, to add paragraphs. [/Post-edit]<p>Tl;dr version: It seems to me you should either use heapsort or plain quicksort; the latter with the sort of optimisations described in the linked article, but not including the fallback to heapsort.<p>Long version:<p>Here's my reasoning for the above:<p>You're either working with lists that are reasonably likely to trigger the worst case of randomised quicksort, or you're not working with such lists. By likely, I mean the probability is not extremely small.<p>Consider the case when the worst case is very unlikely: you're so unlikely to have a worst case that you're gaining almost nothing for accounting for it except extra complexity. So you might as well only use quicksort with optimisations that are likely to actually help.<p>Next is the case that a worst case might actually happen. Again, this is not by chance; it has to be because someone can predict your "random" pivot and screw with your algorithm; in that case, I propose just using heapsort. Why? This might be long, so I apologise. It's because usually when you design something, you design it to a high tolerance; a high tolerance in this case ought to be the worst case of your sorting algorithm. In which case, when designing and testing your system, you'll have to do extra work to tease out the worst case. To avoid doing that, you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort.
This book is one of the most general treatments of parameterized Quicksort available: <a href="http://wild-inter.net/publications/wild-2016.pdf" rel="nofollow">http://wild-inter.net/publications/wild-2016.pdf</a>
Where is a high level description of the algorithm? How is it different from quick sort, it seems quite similar based on a quick observation of the code.
I can see why one might blindly call qsort on already sorted data (when using user input), but why sorted data with one out of place element? Presumably that element has been appended to a sorted array, so you would place it properly in linear time using insertion and not call a sort function at all. Why does such a pattern arise in practice?