News for hackers. Stuff that matters.
Re:Pattern-defeating quicksort by jorgemf on Thursday June 29, 2017 @02:47PM (#14665877)
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.
Re:Pattern-defeating quicksort by klodolph on Thursday June 29, 2017 @02:58PM (#14665966)
The readme file actually contains a fairly thorough description of how it differs from quicksort. Start with the section titled "the best case".
Re:Pattern-defeating quicksort by jorgemf on Thursday June 29, 2017 @04:49PM (#14666748)
> 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.

Re:Pattern-defeating quicksort by _hrfd on Thursday June 29, 2017 @05:02PM (#14666849)
You'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.