Why is quicksort better than other sorting algorithms in practice? (2013)
cs.stackexchange.com
cs.stackexchange.com
(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
for n in array:
sleep(n)
print(n)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.
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.
Or 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.
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.
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.
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.
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.