Disclaimer: I designed the system that won the 2014 GraySort based on Apache Spark, and the same system was extended by a different team to win the 2016 record in cloud sort.&quot;Merge sort is the only algorithm that can effectively be parallelized&quot; is not a good explanation for the lack of quick sort usage in the sort benchmark. In a parallel sorting system, you can decouple the merging step from the sorting of partial runs. That is, you&#x27;d still want the fastest algorithm for sorting partial runs, and then implement a fast merge operation.So what&#x27;s the reason? I can only offer speculations based on my own experience.Contrary to what the name suggests, the sort benchmark is actually not designed primarily to test the in-memory sorting part of the system. It is designed to stress the entire system. When you are required to sort 100TB, or even PBs+ of data, your software system&#x27;s ability to optimize for I&#x2F;O (including reading from&#x2F;writing to disks, sending data across the network, pipelining) is far more important than the actual sorting itself. Of course, you shouldn&#x27;t have a very slow sort algorithm either.The reason I used TimSort was because it was relatively fast, already implemented in Apache Spark, I was really familiar with it, so I could tweak it to do what I needed. The vast majority of the time I spent in the sorting part was to tune memory layout (to make sure there&#x27;s 0 JVM garbage collection, and good cache locality), and to remove any virtual function calls. Once tuned, the sorting time was a very small fraction of the overall time. Using TimSort (which can merge partially sorted runs very quickly) also allowed me to implement just one highly optimized sorting algorithm, rather than having to implement one algorithm for sorting the partial runs, and another algorithm for merging them.The sort benchmark also defines the key space (10 byte key) as fixed length. My guess is that the fastest in-memory sorting algorithm for this case would be a highly optimized radix sort, which the 2016 Gray sort record used.

Weirdly, merge sort might the only sorting algorithm that I learned in school I can actually write without thinking. It&#x27;s very intuitive and simple, at least to me ?

It&#x27;s still one of my favorite things about mergesort that there&#x27;s a variant that can use 4 separate tape drives to sort 2 tapes&#x27; worth of data with barely any working memory.It just streams the data back and forth until it&#x27;s sorted.

Are there any other algorithms that work on data that can&#x27;t all fit into memory? I&#x27;ve used Merge sort multiple times just for that ability.

Big data sorting is a very different problem. At the top level, a merge sort is mandatory, because that&#x27;s the only algorithm that can be effectively parallelized across N nodes.

There are annual contests for sorting large amounts of data, e.g.:<a href="http:&#x2F;&#x2F;sortbenchmark.org&#x2F;" rel="nofollow">http:&#x2F;&#x2F;sortbenchmark.org&#x2F;</a>(I could be wrong but I don&#x27;t think the winners ever used Quicksort.)

I think you might mean selection sort, which picks out elements from the original in sorted order one at a time.Insertion sort has partial results early as well, but they probably wouldn&#x27;t be as useful, the only thing you could report early would be &quot;here&#x27;s the sorted order of the first k elements in the list&quot; (as opposed to the first k elements in sorted order from the whole list, that selection sort gives you).If you really did want online output like that, I think you&#x27;d want to look at heapsort instead.If you compare the worst-case you have O(n) time to prepare the heap (once at the start) and then O(lg n) time to produce each single element of the answer.Selection sort you&#x27;d require O(n) time to produce each element.Selection sort doesn&#x27;t win out in average or best case either. The best you could really hope for is it to win on constant factors, but it&#x27;d be hard for realistic inputs.

Insertion sort is very interesting: as an online algorithm, it is capable of producing partial results.

Sure, but secure RNGs are not cheap. That&#x27;s another trade-off to consider.

Securely random pivot selection would also avoid the DoS.

There are too many different tradeoffs and dimensions to the problem to say that one sorting algorithm is the &quot;best&quot;. E.g. quicksort without fallback has a denial of service attack against it.

Well, nobody really uses plain quicksort in practice (maybe libc qsort?), but a lot of practical fast sort algorithms are variant (or based on) quicksort (including the ips4o you linked to if I&#x27;m reading the paper correctly).A better claim would be that, among the comparison based sorts, algos in the quicksort family tend to be faster in practice.

It&#x27;s not even the fastest comparison-based sorter for the vast majority of inputs. There are much faster sorters out there that exploit the details of modern hardware (branch prediction is a big one, parallelism is also an obvious win if you can make use of it, etc), e.g. <a href="https:&#x2F;&#x2F;github.com&#x2F;SaschaWitt&#x2F;ips4o&#x2F;" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;SaschaWitt&#x2F;ips4o&#x2F;</a> (sequential and parallel, disclaimer: the authors are my colleagues) or <a href="https:&#x2F;&#x2F;github.com&#x2F;orlp&#x2F;pdqsort" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;orlp&#x2F;pdqsort</a> (sequential)

I enjoyed Alexandrescu’s CppCon 2019 talk “Speed Is Found In The Minds of People”About optimizing generic sorting routines for modern hardware.<a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=FJJTYQYB1JQ" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=FJJTYQYB1JQ</a>

I remember learning in my college algorithms class that radix sort is &#x27;slow in practice&#x27; because it&#x27;s &#x27;not cache friendly&#x27; then when we had a sorting speed competition project the fastest entry was a radix sort.

In principle, you can use radix sort for pretty much any real-world data. All you need is a canonical binary &quot;sort key&quot; representation, and you can implement MSD radix sort on top of that. (For variable-length data like strings, the sort key can be a lazy iterator in case you need to break ties for initially equal sort keys, which of course requires MSD not LSD radix sort.) Composite data types can just concatenate the sort keys of their members, recursively, much like we build hash code implementations. At some point I want to release a sorting library which introduces a new Rust trait for this purpose.

That was burst sort, not bubble sort.(That said, bubblesort can be fast if the data are usually very close to sorted - one example here is depth-sorting polygons for a rendering engine on a highly constrained platform.)

Database systems do not operate on large strings and sort by keys rather than whole rows.
And they tend to use hash maps as input invoking truly flat distributions.
They also require sort stability.Burstsort and radix sort are best for cases where you actually sort based on whole or almost whole structure comparison - as in memcmp.Burstsort is also equivalent to walking a trie index in a database. So yes, you see it quite a lot.

Can you elaborate on why bubble sort is fast on huge dataset?Also, If counting based sorting algorithm is faster in practice , why we are not seeing more of it in database system?

Oh my. Comparison sorts are still slower than counting sorts on typical architectures, esp. radix sort. (Coupled with insertion sort of small sizes.)Or burstsort if the data size is truly huge.As usual, StackOverflow is missing the forest for the trees.

Bucket sort can be pretty effective physically. An example would be separating the papers by first initial if you&#x27;re sorting by name (pick whatever matches your sorting key), then sorting each bucket individually (pick whatever seems appropriate, another layer of buckets or just insertion sort for instance). When you&#x27;ve sorted each bucket, you just put the buckets in order, no real merge work needed.You can adapt what you&#x27;re doing by how the buckets look (huge bucket? do another layer of bucketing in there. Small bucket? Just sort it) and it&#x27;s easy to see progress and you can &quot;discard&quot; buckets as you go (put them in one output pile as they&#x27;re done).

I&#x27;ve has the same experience sorting trading cards. I did that frequently and experimented by applying different methods. I found the fastest for human execution was the same as you describe, insertion sort on small groups of 8-10 and then pairwise merge sort the piles until done.

I did the same, but I guessed the optimal number of piles is logarithmic in the number of papers, though I can&#x27;t make further analysis. I naively split into log_e(200) = 5.29 = 5 piles. Also, if you place all the piles within vision, you can merge them all in one go, because the next paper should always be on top of some pile.

I had an interesting experience sorting exam papers when I was a TA. I found that quicksort used up too much desk&#x2F;floor space. I settled on splitting the papers into piles of 10 or so, applying insertion sort on each pile and then pairwise merge sorting them until I had a sorted pile.

And if 1.5x the input fits into memory than merge sort is also better because depending on the input, it ranges from &quot;not slower&quot; to &quot;faster&quot;.This puts quicksort in the position where it&#x27;s only better than merge-sort if the input is larger than 2&#x2F;3 the available memory, but smaller than the total available memory. IIRC, glibc&#x27;s quicksort will do a mergesort if it can do so without increasing the heap size.

if the input doesn&#x27;t fit into memory than usually merge sort is better, because it is sequential and we do not need to jump around

&gt; they found that mergesort was actually faster. I wonder if it has anything to do with how a programming language implements listsIt probably also has to do with using a non-in-place quicksort, which is where it really shines. Even more so as you&#x27;d implement the low arities using an insertion sort rather than a quicksort, which wouldn&#x27;t work either for immutable collections.

Here are some good answers as to why Haskell switched to mergesort<a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;52238049&#x2F;240569" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;52238049&#x2F;240569</a>

I checked the Haskell implementation of sort a while ago. Apparently it used to be Quicksort, which has a really elegant recursive implementation in Haskell, but they found that mergesort was actually faster. I wonder if it has anything to do with how a programming language implements lists, or if people just assume QuickSort is the fastest because of threads like these and don&#x27;t bother trying out alternatives.

Or if I am actually sorting stuff, I&#x27;m using the sort provided by the standard library. I don&#x27;t think I&#x27;ve ever implemented a sort outside of an academic context. Used them plenty of times, but I couldn&#x27;t imagine not using the standard library.Schools talk about sorting algorithms because it&#x27;s instructive, not because they&#x27;re important problems. You can explain the problem in thirty seconds, and even if you explain it badly, everyone will have an intuitive understanding of the problem.Then you can show students intuitive algorithms of insertion sort and selection sort and they&#x27;ll understand the algorithm.Then you time it. Then you show them weird non intuitive algorithms like heap sort or quicksort and show that they&#x27;re a ton faster. Not a lot faster, but like way way way faster.Then your students understand they&#x27;ll need to carefully consider their algorithms and all the ramifications moving forward.If you start a CS101 student with a hard algorithms problem they&#x27;ll switch majors. And that will be your fault for being a shitty teacher, not their fault for being lazy or dumb.

The thing that always bothers me about these sort tests is that once I got out of college I&#x27;ve hardly ever sorted numbers, either because the data isn&#x27;t numeric or the API I&#x27;m calling does it for me.I&#x27;m sorting text, or I&#x27;m sorting dates. Or I&#x27;m doing a compound sort, where it&#x27;s dates, then text, then numbers. It&#x27;s rare to me to see a benchmark where the compare() operation is accounted for. It is not difficult at all for the complexity of the compare() operation to trend toward log(n), causing an algorithm with a tighter upper bound on number of comparisons but high constant overhead to perform better.I presume we can vectorize string comparisons at this point? How would we handle compound sorts with SIMD operations?

&gt; for scar execution.Do you mean scalar execution?

*for scar execution.SIMD and GPGPU record-breaking parallel implementations use radix, bitonic, etc.

People usually choose quicksort because it is in-place and there are simple mitigations for inputs that exhibit poor performance.

Interesting. The man page just says &quot;sort an array&quot;.
<a href="https:&#x2F;&#x2F;linux.die.net&#x2F;man&#x2F;3&#x2F;qsort" rel="nofollow">https:&#x2F;&#x2F;linux.die.net&#x2F;man&#x2F;3&#x2F;qsort</a>

Libc qsort() isn&#x27;t quicksort in several of the popular libc implementations. For example, it&#x27;s (usually) a merge sort in glibc. <a href="http:&#x2F;&#x2F;calmerthanyouare.org&#x2F;2013&#x2F;05&#x2F;31&#x2F;qsort-shootout.html" rel="nofollow">http:&#x2F;&#x2F;calmerthanyouare.org&#x2F;2013&#x2F;05&#x2F;31&#x2F;qsort-shootout.html</a>

Because it is available in almost every standard library?In most cases developers don&#x27;t care for the worst case because they either have no idea what you are talking about or, if they actually understand the problem, they try to ensure they don&#x27;t need to sort arbitrary amount of user-controllable data.

Why is quicksort better than other sorting algorithms in practice? (2013)