Implementation of Pure Dual Pivot Quick Sort
Tests created in pawsort_tests
NEW DIFFERENTIAL REVISION
- Describe the changes in this new revision. # Included commits in branch T1225_DPQS: # 10a6eb30e684 T1225 - Implemented Pure Dual Pivot Quick Sort.
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.