Page MenuHomePhabricator

Closed, CompletedPublic4 Energy Points (d+f*r)


Our implementation of introsort needs to merge the following concepts:

  • Introspective Sort, which combines heap sort and quicksort to prevent excessive recursion.
  • Dual-Pivot Quicksort, which has marked gains over traditional Quicksort.
  • Heap Sort (see above)
  • New algorithm for selecting pivot points, based on median-of-three.

This is historic for two reasons!

  • This appears to be the first open-source implementation of the Dual-Pivot Quicksort.
  • This is the first time Introsort has been combined with Quicksort, thereby creating a new sorting algorithm!


Task Type
Proposed Urgency
g4: Significant
f3: Off-Road
r3: Moderate
Volatility (Caught At)
Not a Bug
Not a Bug/Unknown

Revisions and Commits

Event Timeline

jcmcdonald edited projects, added Unknown Object (Project); removed PawLIB [Project].Mar 15 2016, 7:19 PM
jcmcdonald lowered the priority of this task from p4: Now to p2: Later.Apr 29 2016, 2:44 PM
jcmcdonald lowered the priority of this task from p2: Later to p1: Eventual.Sep 13 2016, 9:17 AM

I've been in contact with Vladamir Yaroslavisky, the creator of DPQS, and Sebastian Wild, a CS PhD who wrote his thesis on the algorithm. We've been trying (unsuccessfully so far) to coordinate our schedules to republish the original whitepaper, revised, along with a fully open-source implementation of the algorithm. If this working combined algorithm can be completed, that'll probably help. (Of course, proper credit goes to anyone who helps, so I'll keep you in that loop since you're working on this now too.)

jcmcdonald added a subscriber: jcmcdonald.

I'll hand this task off to you, then, for the initial stable version. If you run into trouble, ping me. I'll assist mostly when we get to the "optimization" phase of this.

lulu731 set Volatility (Caught At) to Not a Bug.
lulu731 set Origin to Not a Bug/Unknown.