4 ms·
Where is a high level description of the algorithm? How is it different from quick sort, it seems quite similar based on a quick observation of the code.
by jorgemf 9y ago
Where is a high level description of the algorithm? How is it different from quick sort, it seems quite similar based on a quick observation of the code.
- klodolph 9y agoThe readme file actually contains a fairly thorough description of how it differs from quicksort. Start with the section titled "the best case".
- jorgemf 9y ago> On average case data where no patterns are detected pdqsort is effectively a quicksort that uses median-of-3 pivot selection So basically is quicksort with a bit more clever pivot selection, but only for some cases.
- _hrfd 9y agoYou're forgetting probably the most important optimization: block partitioning. This one alone makes it almost 2x faster (on random arrays) than typical introsort when sorting items by an integer key.