Yet another DPQ update

Joshua Bloch jjb at
Mon Dec 7 20:32:45 UTC 2009


Hi.  Here's another update for Dual Partition Quicksort:

Summary of changes:

 * Improved comments throughout

 * Minor code changes for clarity (e.g., swapped order of some comparisons)

 * Further optimized partitioning performance

 * Restored sentinel optimization in "pivots are equal" case that was
   accidentally deleted. Added comment so it won't be deleted again.

This version (12i) is about 3% faster than version 12a on random data,
10-30% faster on duplicate-rich data, and 1-3% slower on pre-sorted
(ascending/descending) data:

     The DPQ team (Vladimir, Jon, and Josh)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the core-libs-dev mailing list