It'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. https://github.com/SaschaWitt/ips4o/ (sequential and parallel, disclaimer: the authors are my colleagues) or https://github.com/orlp/pdqsort (sequential)
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'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.
Yeah, my implicit comparison was to something like std::sort from GNU's libstdc++, which is introsort, a quicksort-insertionsort-hybrid. Plain quicksort is indeed not great.
ips4o is a samplesort-derivative (the name stands for Inplace Super-Scalar Sample SOrt), which is kinda quicksort-derived, but doesn't use one pivot, but many (in the case of ips4o, 255, iirc). It's heritage traces back to quicksort, if you will, but it's also very different.
(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.)
Another example application of adaptive sorts is the sweep-and-prune broadphase collision detection algorithm that's somewhat commonly used in physics engines.
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.
I remember learning in my college algorithms class that radix sort is 'slow in practice' because it's 'not cache friendly' 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 "sort key" 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.
There are too many different tradeoffs and dimensions to the problem to say that one sorting algorithm is the "best". E.g. quicksort without fallback has a denial of service attack against it.
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't be as useful, the only thing you could report early would be "here's the sorted order of the first k elements in the list" (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'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'd require O(n) time to produce each element.
Selection sort doesn'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'd be hard for realistic inputs.
I think the poster means you aren't given the completed set. Elements come dribbling in a few at a time. With insertion sort, you're able to say, "this is the sorted list at the time we know it right now." Obviously when you get the next element, you don't have a sorted list anymore; you have a sorted list and one extraneous element. But then you apply insertion sort iteration and have a sorted list again.
If that is the goal, BST sort might be a good idea as well (put elements into a balanced binary search tree as you receive them). Not _quite_ the same semantics (you don't have an array exactly at each step), but much faster asymptotics and should be able to answer any queries you'd be doing anyway.
One thing to keep in mind is that it's surprisingly common for a sorted array to outperform a binary search tree because of cache locality and pointer indirection being slow, even though random inserts into arrays are slow. Especially for small sets or when reads greatly outnumber writes. Boost has flat_map and flat_set for this.
It kinda is. Use your operating system to get 128 random bits, use that as a key to AES, use AES-NI instructions to generate boat loads of more bits. These instructions can generate random bits faster than RAM can store them.
Honestly, most of us mortals can operate on the assumption that thread local mt19937 PRNGs seeded with 19,937 OS provided secure bits is safe enough for secure quicksort pivot selection DOS protection, even if we can't generate crypto keys or nonces from it.
The thing that always bothers me about these sort tests is that once I got out of college I've hardly ever sorted numbers, either because the data isn't numeric or the API I'm calling does it for me.
I'm sorting text, or I'm sorting dates. Or I'm doing a compound sort, where it's dates, then text, then numbers. It'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?
Or if I am actually sorting stuff, I'm using the sort provided by the standard library. I don't think I've ever implemented a sort outside of an academic context. Used them plenty of times, but I couldn't imagine not using the standard library.
Schools talk about sorting algorithms because it's instructive, not because they'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'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're a ton faster. Not a lot faster, but like way way way faster.
Then your students understand they'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'll switch majors. And that will be your fault for being a shitty teacher, not their fault for being lazy or dumb.
Because it is available in almost every standard library?
In most cases developers don'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't need to sort arbitrary amount of user-controllable data.
Maybe it's interesting to know what qsort does under the hood? Maybe you don't know what qsort's time and memory constraints are unless you know the underlying algorithim.
Obviously the sorting algorithim you use matters, so this post has some theoretical value.
I had an interesting experience sorting exam papers when I was a TA. I found that quicksort used up too much desk/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.
I'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.
Bucket sort can be pretty effective physically. An example would be separating the papers by first initial if you'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've sorted each bucket, you just put the buckets in order, no real merge work needed.
You can adapt what you're doing by how the buckets look (huge bucket? do another layer of bucketing in there. Small bucket? Just sort it) and it's easy to see progress and you can "discard" buckets as you go (put them in one output pile as they're done).
In a way, quick sort, radix sort and merge sort are all just recursive versions of bucket sort :-)
* Merge sort: sort within buckets, then between buckets
* Quick sort: sort between buckets, then within buckets.
* Radix sort: can be either depending on whether you sort by most or least significant radix first.
Humans can handle dividing into more than 2 at each stage though, so sorting 100 things with 10 piles of 10 tends to be easier than 7 binary divisions.
I did the same, but I guessed the optimal number of piles is logarithmic in the number of papers, though I can'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.
And if 1.5x the input fits into memory than merge sort is also better because depending on the input, it ranges from "not slower" to "faster".
This puts quicksort in the position where it's only better than merge-sort if the input is larger than 2/3 the available memory, but smaller than the total available memory. IIRC, glibc's quicksort will do a mergesort if it can do so without increasing the heap size.
Big data sorting is a very different problem. At the top level, a merge sort is mandatory, because that's the only algorithm that can be effectively parallelized across N nodes.
Weirdly, merge sort might the only sorting algorithm that I learned in school I can actually write without thinking. It's very intuitive and simple, at least to me ?
it would be more impressive if you could implement Sleepsort in your sleep
For those aren't familiar with sleepsort, it looks something like this, where you use whatever concurrency is available in your programming language of choice to execute the for-loop in parallel
Mergesort is more intuitive than selection sort, insertion sort, bubble sort, etc? I highly doubt you can write merge sort without thinking about it. And I highly doubt you can write bug free merge sort without thinking about it. Merge sort and quick sort are notorious for bugs introduced by trying to keep track of the indexes.
> It's very intuitive and simple, at least to me ?
Once you understand mergesort, you have a eureka moment and it all makes sense. But I've never met anyone who thought merge sort was intuitive and simple - especially when learning it the first time.
Didn't say I could it do bug free (c-fashion like), but _correctly_ on paper in an algo exam in pseudo ? Yes.
Also, for future readers, this wasn't a flex, it was intended as an observation of weird things about brains, I learned many sorting algo (like many readers here) and only merge sort kinda stuck.
Yes, I meant sorting algorithms in particular - I thought that was obvious by the context. I don't have a copy of Knuth, but thanks for the link. I'm not surprised that this is a well known problem, but you don't hear much about it.
This reminds me of the first task I had at a new job. The company had a cross-assembler for their custom processor that ran on a PDP-11 with a 65KB total task space. I was told to add an option to turn off the cross reference output, because it was taking 30 minutes to add it to a 2 minute assembly run.
Before starting I decided to figure out why the cross reference was taking so long. Each reference was added to a dynamic memory array, until the memory was filled and then the references were written to a disk file instead. At the end of the assembly, the array was sorted with a Bubble sort. Then for each symbol in the symbol table, the table and file were read linearly to find each reference for that symbol. This was an O(n^2) process - no wonder it was so slow!
I took out the Bubble sort and did a Merge sort on the file, then read the file to create the cross reference directly since it was in the proper order. When the time went from 30 minutes to 30 seconds, suddenly it wasn't important to have an option to turn it off anymore.
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.
"Merge sort is the only algorithm that can effectively be parallelized" 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'd still want the fastest algorithm for sorting partial runs, and then implement a fast merge operation.
So what'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's ability to optimize for I/O (including reading from/writing to disks, sending data across the network, pipelining) is far more important than the actual sorting itself. Of course, you shouldn'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'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.
It's still one of my favorite things about mergesort that there's a variant that can use 4 separate tape drives to sort 2 tapes' worth of data with barely any working memory.
It just streams the data back and forth until it's sorted.
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't bother trying out alternatives.
> they found that mergesort was actually faster. I wonder if it has anything to do with how a programming language implements lists
It probably also has to do with using a non-in-place quicksort, which is where it really shines. Even more so as you'd implement the low arities using an insertion sort rather than a quicksort, which wouldn't work either for immutable collections.
67 comments
[ 3.5 ms ] story [ 120 ms ] threadOr burstsort if the data size is truly huge.
As usual, StackOverflow is missing the forest for the trees.
About optimizing generic sorting routines for modern hardware.
https://www.youtube.com/watch?v=FJJTYQYB1JQ
A better claim would be that, among the comparison based sorts, algos in the quicksort family tend to be faster in practice.
ips4o is a samplesort-derivative (the name stands for Inplace Super-Scalar Sample SOrt), which is kinda quicksort-derived, but doesn't use one pivot, but many (in the case of ips4o, 255, iirc). It's heritage traces back to quicksort, if you will, but it's also very different.
Also, If counting based sorting algorithm is faster in practice , why we are not seeing more of it in database system?
(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.)
Another example application of adaptive sorts is the sweep-and-prune broadphase collision detection algorithm that's somewhat commonly used in physics engines.
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.
Insertion sort has partial results early as well, but they probably wouldn't be as useful, the only thing you could report early would be "here's the sorted order of the first k elements in the list" (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'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'd require O(n) time to produce each element.
Selection sort doesn'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'd be hard for realistic inputs.
If that is the goal, BST sort might be a good idea as well (put elements into a balanced binary search tree as you receive them). Not _quite_ the same semantics (you don't have an array exactly at each step), but much faster asymptotics and should be able to answer any queries you'd be doing anyway.
One thing to keep in mind is that it's surprisingly common for a sorted array to outperform a binary search tree because of cache locality and pointer indirection being slow, even though random inserts into arrays are slow. Especially for small sets or when reads greatly outnumber writes. Boost has flat_map and flat_set for this.
Honestly, most of us mortals can operate on the assumption that thread local mt19937 PRNGs seeded with 19,937 OS provided secure bits is safe enough for secure quicksort pivot selection DOS protection, even if we can't generate crypto keys or nonces from it.
SIMD and GPGPU record-breaking parallel implementations use radix, bitonic, etc.
Do you mean scalar execution?
I'm sorting text, or I'm sorting dates. Or I'm doing a compound sort, where it's dates, then text, then numbers. It'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?
Schools talk about sorting algorithms because it's instructive, not because they'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'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're a ton faster. Not a lot faster, but like way way way faster.
Then your students understand they'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'll switch majors. And that will be your fault for being a shitty teacher, not their fault for being lazy or dumb.
In most cases developers don'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't need to sort arbitrary amount of user-controllable data.
Obviously the sorting algorithim you use matters, so this post has some theoretical value.
You can adapt what you're doing by how the buckets look (huge bucket? do another layer of bucketing in there. Small bucket? Just sort it) and it's easy to see progress and you can "discard" buckets as you go (put them in one output pile as they're done).
* Merge sort: sort within buckets, then between buckets
* Quick sort: sort between buckets, then within buckets.
* Radix sort: can be either depending on whether you sort by most or least significant radix first.
Humans can handle dividing into more than 2 at each stage though, so sorting 100 things with 10 piles of 10 tends to be easier than 7 binary divisions.
This puts quicksort in the position where it's only better than merge-sort if the input is larger than 2/3 the available memory, but smaller than the total available memory. IIRC, glibc's quicksort will do a mergesort if it can do so without increasing the heap size.
http://sortbenchmark.org/
(I could be wrong but I don't think the winners ever used Quicksort.)
For those aren't familiar with sleepsort, it looks something like this, where you use whatever concurrency is available in your programming language of choice to execute the for-loop in parallel
It is one of the rare algorithms that is equally good when run by a computer and by hand.
> It's very intuitive and simple, at least to me ?
Once you understand mergesort, you have a eureka moment and it all makes sense. But I've never met anyone who thought merge sort was intuitive and simple - especially when learning it the first time.
Also, for future readers, this wasn't a flex, it was intended as an observation of weird things about brains, I learned many sorting algo (like many readers here) and only merge sort kinda stuck.
There are many - this has been an area of study since CS began. Have a look at vol 3 of Knuth, for starters.
Also, https://en.wikipedia.org/wiki/External_sorting talks about distribution sort; there are others.
Before starting I decided to figure out why the cross reference was taking so long. Each reference was added to a dynamic memory array, until the memory was filled and then the references were written to a disk file instead. At the end of the assembly, the array was sorted with a Bubble sort. Then for each symbol in the symbol table, the table and file were read linearly to find each reference for that symbol. This was an O(n^2) process - no wonder it was so slow!
I took out the Bubble sort and did a Merge sort on the file, then read the file to create the cross reference directly since it was in the proper order. When the time went from 30 minutes to 30 seconds, suddenly it wasn't important to have an option to turn it off anymore.
"Merge sort is the only algorithm that can effectively be parallelized" 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'd still want the fastest algorithm for sorting partial runs, and then implement a fast merge operation.
So what'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's ability to optimize for I/O (including reading from/writing to disks, sending data across the network, pipelining) is far more important than the actual sorting itself. Of course, you shouldn'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'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.
It just streams the data back and forth until it's sorted.
It probably also has to do with using a non-in-place quicksort, which is where it really shines. Even more so as you'd implement the low arities using an insertion sort rather than a quicksort, which wouldn't work either for immutable collections.
https://stackoverflow.com/a/52238049/240569