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!