News for hackers. Stuff that matters.
Re:Why is quicksort better than other sorting algorithms in ... by amelius on Monday January 20, 2020 @10:26AM (#22099426)
There are annual contests for sorting large amounts of data, e.g.:

http://sortbenchmark.org/

(I could be wrong but I don't think the winners ever used Quicksort.)

Re:Why is quicksort better than other sorting algorithms in ... by SpicyLemonZest on Monday January 20, 2020 @10:51AM (#22099644)
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.
Re:Why is quicksort better than other sorting algorithms in ... by rxin on Monday January 20, 2020 @02:20PM (#22101378)
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.

Re:Why is quicksort better than other sorting algorithms in ... by jrimbault on Monday January 20, 2020 @11:45AM (#22100043)
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 ?
Re:Why is quicksort better than other sorting algorithms in ... by GuB-42 on Monday January 20, 2020 @01:57PM (#22101213)
Mergesort is used routinely by people who know nothing about programming. For example, it is used by teachers to sort exam papers by grade.

It is one of the rare algorithms that is equally good when run by a computer and by hand.

Re:Why is quicksort better than other sorting algorithms in ... by lenkite on Monday January 20, 2020 @01:53PM (#22101182)
You are not the only one. Merge sort and insertion sort are deeply intuitive sorts. Quicksort is not.
Re:Why is quicksort better than other sorting algorithms in ... by klyrs on Monday January 20, 2020 @01:37PM (#22101048)
Weird flex: I can implement bogosort in my sleep...
Re:Why is quicksort better than other sorting algorithms in ... by xvector on Monday January 20, 2020 @01:52PM (#22101172)
I implement cosmic-ray-bit-flip-bogo-sort in every program I write!
Re:Why is quicksort better than other sorting algorithms in ... by Rebelgecko on Monday January 20, 2020 @05:14PM (#22102519)
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

    for n in array:
        sleep(n)
        print(n)
Re:Why is quicksort better than other sorting algorithms in ... by skzo on Monday January 20, 2020 @12:34PM (#22100467)
Insertion sort is very intuitive and simple as well
Re:Why is quicksort better than other sorting algorithms in ... by wolco on Monday January 20, 2020 @01:16PM (#22100837)
The bubble sort just writes itself.
Re:Why is quicksort better than other sorting algorithms in ... by jrimbault on Monday January 20, 2020 @01:46PM (#22101124)
Definitely yes, but I can't write it without thinking like merge sort ¯\_(ツ)_/¯
Re:Why is quicksort better than other sorting algorithms in ... by elfexec on Monday January 20, 2020 @06:23PM (#22102898)
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.

Re:Why is quicksort better than other sorting algorithms in ... by jrimbault on Tuesday January 21, 2020 @06:22AM (#22105943)
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.

Re:Why is quicksort better than other sorting algorithms in ... by hinkley on Monday January 20, 2020 @03:22PM (#22101825)
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.

Re:Why is quicksort better than other sorting algorithms in ... by mark-r on Monday January 20, 2020 @12:07PM (#22100231)
Are there any other algorithms that work on data that can't all fit into memory? I've used Merge sort multiple times just for that ability.
Re:Why is quicksort better than other sorting algorithms in ... by ska on Monday January 20, 2020 @12:17PM (#22100329)
Do you mean other sorting algorithms, or other out-of-core algorithms in general?

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.

Re:Why is quicksort better than other sorting algorithms in ... by mark-r on Monday January 20, 2020 @12:45PM (#22100568)
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.
Re:Why is quicksort better than other sorting algorithms in ... by ska on Monday January 20, 2020 @03:06PM (#22101704)
Early algorithm development thought about this quite a bit because system memory was really constrained.
Re:Why is quicksort better than other sorting algorithms in ... by mark-r on Monday January 20, 2020 @04:47PM (#22102344)
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.