A variant of quicksort which switches to heapsort when necessary.

A common problem with quicksort is that, when coded in the naive way, it performs most poorly on pathological inputs such as an already-sorted list. Introspection sort does away with this liability by switching to an algorithm (heapsort) that has a better worst-case performance than quicksort when the input set is close to pathological.

The specifications for the C++ Standard Template Library require that sorting be done in O(n lg n) time; the introduction of introsort has allowed software vendors such as Silicon Graphics to include quicksort support in the STL. It has also been incorporated into GNU's C++ implementation and to Boris Fomitchev's STLport, which makes SGI's STL available on many different platforms.