Fwd: [libstdc++] pdqsort - a faster std::sort

[Orson Peters]

Woops, didn't intend this to be a personal reply. Forwarded email:

It's not so much novel that it's hard to analyze, or anything to be
nervous about. It's very similar
to introsort in that it is quicksort with heuristics/optimizations
tacked on. The combination of
optimizations used is novel.

The code with comments is only 300LOC, so even rigorous manual
verification with pre/post conditions
is possible.

Most heuristics used are not novel, only (to my knowledge) three of
them are, and they are trivial to
show to be safe. I'd definitely suggest you to read the readme
(https://github.com/orlp/pdqsort) to
see the heuristics explained in detail.

In a very brief summary, pdqsort is quicksort with the following enhancements:

 - Use median of 3 pivot selection. (libstdc++ std::sort does this)
 - Switch to insertion sort for small partitions. (libstdc++ std::sort
does this)
 - Put equal elements on the left unless equal to pivot, then filter.
(qsort in glibc does this)
 - Attempt insertion sort if partition swapped no elements. (libc++
std::sort does this)
 - Only attempt above insertion sort if partition was not highly
unbalanced. (novel)
 - Shuffle 8 elements elements on highly unbalanced partition. (novel)
 - Only decrement counter to switch to heapsort on highly unbalanced
partition. (novel)



2015-04-07 15:50 GMT+02:00 Jonathan Wakely <jwakely@redhat.com>:
> On 07/04/15 15:44 +0200, Orson Peters wrote:
>>
>> I'd like to present pattern-defeating quicksort, a novel sorting
>> algorithm.
>
>
> I'd be nervous about switching to a novel algorithm rather than a
> well-known one that has stood the test of time, but this isn't my area
> of expertise so I'll leave it to others to make any more substantial
> comments.
>