News for hackers. Stuff that matters.

A comment on Pattern-defeating quicksort. Parent comment

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.

[ Parent | on HN ]
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.
[ Parent | on HN ]