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!