4 ms·
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 http://lkozma.net/i
by lkozma 4y ago
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 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/ http://lkozma.net/blog/a-dual-view-of-sorting-algorithms/
- thanatos519 4y agoThat is great and should be in every textbook!
- raddan 4y agoThere'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.")
- lkozma 4y agoYes, 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).
- chongli 4y agoYes 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!
- ro_jazz 4y agoSuper cool!
- robswc 4y agoThis 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!
- Ono-Sendai 4y agoQuickSort should be called PartitionSort - it would make this duality more obvious.
- gardenhedge 4y agoWhat's the significance of this?
- complex_exp 4y agoIt's cool.
- kzrdude 4y agoHow do we understand, inside this model, that merge sort is easily stable but quicksort is not a stable sort?