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

[Orson Peters]

Oh and I forgot to mention, pdqsort does not improve on std::sort by a
factor of '2ish' on ascending data.

For ascending, descending and all-equal inputs pdqsort is linear and
does 2n or 3n operations.

2015-04-08 11:35 GMT+02:00 Christopher Jefferson <chris@bubblescope.net>:
> I have thought for a while that std::sort could probably due with
> improvements in this direction, particularly for almost-sorted data
> (although std::sort is doing better than I thought it might! You still
> improve by a factor of 2ish). The code is also pleasingly short.
>
> While I don't have any sole control, I would be happy to see this
> merged, under the following conditions (I reserve the right to add
> more during more careful review!)
>
>
> * I assume the sort works on move-only types in C++11? (I can see you
> make use of move, but do you require it?).
>   - There was a reason (and I can't remember what it was now!) that we
> used 'iter_swap' rather than 'swap(*a,*b)' on iterators. I think it
> might be required to allow sorting std::vector<bool>? Either way, it
> might be worth trying it.
>   - In general, try adding your code to libstdc++ (just replace
> std::sort with your function), and run the test suite and see what
> falls out!
>
> * Would be nice to see benchmarks on more types (strings and deques
> are two obvious candidates. Also make them reasonably long with long
> equal prefixes, to make the comparison function more expensive).
>
> Chris
>
>
>
> On 7 April 2015 at 15:24, Orson Peters <orsonpeters@gmail.com> wrote:
>> 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.
>>>