Page MenuHomePhabricator

T1225 - Implemented Pure Dual Pivot Quick Sort.

Authored by lulu731 on Jan 12 2020, 7:49 AM.



Implementation of Pure Dual Pivot Quick Sort

Test Plan

Tests created in pawsort_tests

Revert Plan


  1. Describe the changes in this new revision. # Included commits in branch T1225_DPQS: # 10a6eb30e684 T1225 - Implemented Pure Dual Pivot Quick Sort.

Diff Detail

Lint Not Applicable

Event Timeline

Build is green

Building PawLIB on mpm-bionic-000929oczuya1 as build 535.
Running test suite P-sB30.

See for more details.

Restricted Application completed remote builds in Restricted Buildable.Jan 12 2020, 7:50 AM
jcmcdonald added subscribers: iaroslavski, jcmcdonald.

I am so out of touch with the sorting algorithms right now, it's not even funny. I'm going to have to refresh myself properly. Meanwhile, except for possibly switching from thirds to median-of-three for pivots, this is probably a good starting position.

Meanwhile, have we looked into the performance implications of std::iter_swap? I know we were debating about how to swap values some time back, but I can't remember the conclusions. (If I remember correctly, @iaroslavski was involved in that discussion...maybe we should get him involved again?)


One of the key components of the performance of DPQS comes down to these pivot points. See 653-662.

This revision now requires changes to proceed.Jan 13 2020, 6:48 PM

By the way, I've added Sebastian Wild's thesis on Dual-Pivot Quicksort to the Files wiki. I suspect we'd both benefit from a perusal if we're going to achieve our goal.

Although it can be improved, we can go ahead and just land this. The entire sorting library here will need refactor anyway, and this will be a good starting position for DPQS.

This revision is now accepted and ready to land.May 22 2020, 4:22 PM
This revision was automatically updated to reflect the committed changes.

There was a major error in this that I missed. I reimplemented your changes (for the most part). I reimplemented in rP14bd156133e9: Reimplement D263 (on behalf of lulu731)