Hacker News Reader

Comment by lkozma | Hacker News Reader

May I add one that I made?

Illustration of QuickSort and MergeSort as two sides of the same coin: http://lkozma.net/images/sort/duality.pdf

I find this somehow both obvious and counter-intuitive, and usually the two algorithms are not presented in this way, as duals of each other.

I wrote up this view in more detail, but the figure above should be self-explanatory: http://lkozma.net/blog/a-dual-view-of-sorting-algorithms/

View on HN

There's an important distinction that your explanation glosses over, which is that MergeSort is an out-of-place sort while QuickSort is in-place. As a practical matter, this distinction is important and it makes the two algorithms not quite duals. Your explanation of why we can assume that QuickSort pivots are medians makes sense, but it also glosses over one of the deep insights about why QuickSort works at all, which is that with unsorted data, the choice of pivot will rarely be bad (it will be "near the middle on average.")

Yes, this efficiency-aspect is not captured in the illustration -- while splitting perfectly _by index_ comes for free, splitting perfectly _by value_ needs nontrivial work (median-finding).

Yes and with naïve median-finding comes pathological inputs that hit the worst case O(n^2). Something to watch out for if you’re sorting user-provided input as that could open you up to some silly denial of service attacks!

QuickSort should be called PartitionSort - it would make this duality more obvious.

This is awesome. I think ppl should def share anything they made. As long as its not low-effort shilling... and your contributions are anything but!

That is great and should be in every textbook!

How do we understand, inside this model, that merge sort is easily stable but quicksort is not a stable sort?

What's the significance of this?

It's cool.

Super cool!

Reply on news.ycombinator.com