This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[libstdc++] pdqsort - a faster std::sort
- From: Orson Peters <orsonpeters at gmail dot com>
- To: libstdc++ at gcc dot gnu dot org
- Date: Tue, 7 Apr 2015 15:44:01 +0200
- Subject: [libstdc++] pdqsort - a faster std::sort
- Authentication-results: sourceware.org; auth=none
I'd like to present pattern-defeating quicksort, a novel sorting algorithm.
It is as fast or faster than std::sort on any implementation I've tested
(libstdc++, libc++, VS2013) for both random data and a variety of patterns
(equal, asc/desc, pipe organ, etc).
A short explanation of the design of pdqsort can be found in the readme:
https://github.com/orlp/pdqsort .
The code of pdqsort is very short (~300LOC) and clean. Understanding
pdqsort and integration should be painless.
I'm willing to prepare a patch and do the legal wizardry required to
integrate pdqsort as std::sort in libstdc++, if the interest is there.
If you have any questions after reading the readme, please do reply and I
will do my best to answer them.
Greetings,
Orson Peters
P.S.: I submitted the same code to the libc++ mailing list. AFAIK there are
no license issues with committing the code to both projects.