3 ms·

Well, it came out a while ago, so maybe we can be a bit silly: There’s something sort of beautiful about mergesort and heapsort. Their names tell you what thei

Well, it came out a while ago, so maybe we can be a bit silly: There’s something sort of beautiful about mergesort and heapsort. Their names tell you what their main idea is, and how they work is immediately obvious. Quicksort, on the other hand, has nothing beautiful about it and is named after it’s one redeeming feature (that it is quick for a lot of cases).

thesz 17d ago
The beauties of quicksort are that it sorts in-place and that it is embarrassingly simple. The in-place property can be utilized to make it very close to cache-oblivious algorithm.
teiferer 17d ago
How is it less beautiful? Honest question, curious to hear about what that means to you.
- drdexebtjl 17d ago
  To me it’s the fact that if you try to do it in real life (sorting a collection of objects in the real world), you just end up doing merge sort by accident. It feels like an optimization of merge sort for computers, rather than a different approach. This is also reflected in the way that it’s usually taught. Normally merge sort is presented first, and quick sort follows from observations about what would happen if you picked different partition points instead of dividing them in half, and how you can reduce the additional space requirements.
- bee_rider 17d ago
  Just look at the little video on Wikipedia, it is an absolute mess of elements being thrown around. Chaos. Real answer: I tutored beginner programming students for a bit and I guess I just thought quicksort didn’t fit in very well. Mergesort is an elegant and straightforward example of recursion. Heapsort—you can make a priority queue and then if you plop a heap in there, that’s heapsort. I like the story. With quicksort, it isn’t that complicated or anything but it doesn’t feel like it embodies an idea in the way the other two do. And it is annoying that the real big-O cost of the popular sorting algorithm is n^2, and the bad case is really obvious. I guess there’s value to getting over the hump of “well heuristics are a thing and big-O doesn’t tell you everything” but I still don’t like it.
rodrigosetti 17d ago
Maybe if Hoare had called it Partitionsort in 1960, the name wouldn’t have been memorable enough to catch on and become so popular.

thesz 17d ago

The beauties of quicksort are that it sorts in-place and that it is embarrassingly simple. The in-place property can be utilized to make it very close to cache-oblivious algorithm.

teiferer 17d ago

How is it less beautiful? Honest question, curious to hear about what that means to you.

drdexebtjl 17d ago
To me it’s the fact that if you try to do it in real life (sorting a collection of objects in the real world), you just end up doing merge sort by accident. It feels like an optimization of merge sort for computers, rather than a different approach. This is also reflected in the way that it’s usually taught. Normally merge sort is presented first, and quick sort follows from observations about what would happen if you picked different partition points instead of dividing them in half, and how you can reduce the additional space requirements.
bee_rider 17d ago
Just look at the little video on Wikipedia, it is an absolute mess of elements being thrown around. Chaos. Real answer: I tutored beginner programming students for a bit and I guess I just thought quicksort didn’t fit in very well. Mergesort is an elegant and straightforward example of recursion. Heapsort—you can make a priority queue and then if you plop a heap in there, that’s heapsort. I like the story. With quicksort, it isn’t that complicated or anything but it doesn’t feel like it embodies an idea in the way the other two do. And it is annoying that the real big-O cost of the popular sorting algorithm is n^2, and the bad case is really obvious. I guess there’s value to getting over the hump of “well heuristics are a thing and big-O doesn’t tell you everything” but I still don’t like it.

rodrigosetti 17d ago

Maybe if Hoare had called it Partitionsort in 1960, the name wouldn’t have been memorable enough to catch on and become so popular.