Introsort

Introsort is a hybrid, comparison-based sorting algorithm that combines quicksort, heapsort, and insertion sort to achieve fast average performance with a guaranteed worst-case running time. It was introduced by David Musser in 1997 as part of the design of the C++ standard library's sorting routines.

The algorithm starts by performing quicksort partitioning on the input array. It tracks the recursion depth and uses a depth limit proportional to the logarithm of the input size. If the depth limit is exceeded, the algorithm switches to heapsort for the remaining elements to avoid the quadratic worst case of quicksort. For small subarrays, typically below a threshold such as 16 elements, insertion sort is applied to reduce overhead and improve practical speed. Pivot selection strategies, such as median-of-three, can be employed to improve partition quality.

Introsort is not a stable sort. Its in-place, recursive approach has a space complexity of O(log n) due to recursion, and its overall time complexity is O(n log n) in the worst and average cases, with insertion sort contributing to practical speed on small runs.

In modern standard libraries, introsort is used for the primary sort routine, notably in the C++ standard library's std::sort implementation in many compilers. Variants and refinements exist, but the basic principle remains: blend quicksort speed with heapsort worst-case guarantees and insertion sort optimization.