Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort, switching to heapsort once the recursion depth exceeds a preset value. The resulting sort combines the best of both, with a worst-case O(n log n) runtime and practical performance comparable to quicksort on typical data sets. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes O(n log n) comparisons to sort n items. ... Heapsort is one of the best general-purpose sort algorithms, and is part of the selection sort family. ... In complexity theory, computer science, and mathematics the Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

Musser reported that on a median-of-3 killer sequence of 100,000 elements, introsort's running time was 1/200th that of median-of-3 quicksort. Musser also considered the effect on caches of Sedgewick's delayed small sorting, where small ranges are sorted at the end in a single pass of insertion sort. He reported that it could double the number of cache misses, but that its performance with double-ended queues was significantly better and should be retained for template libraries, in part because the gain in other cases from doing the sorts immediately was not great. Diagram of a CPU memory cache A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. ... Insertion sort is a simple sort algorithm in which the sorted array (or list) is built one entry at a time. ...

The June 2000 SGI C++ Standard Template Library stl_algo.c (http://www.sgi.com/tech/stl/stl_algo.h) implementation of unstable sort uses the Musser introsort approach with the recursion depth to switch to heapsort passed as a parameter, median-of-3 pivot selection and the Sedgewick final insertion sort pass. The element threshold for switching to the simple insertion sort was 16. Current Silicon Graphics logo. ... The Standard Template Library (STL) is a software library. ...

The C++ STL implementations generally significantly (several times as fast) outperform the C implementation because they are implemented to allow inlining, while the generic C equivalent must use function calls for comparisons. This advantage could be compensated for by using custom versions of the sort function, at the cost of losing the advantage of a totally generic library function.

References

• David Musser. Introspective Sorting and Selection Algorithms (http://www.cs.rpi.edu/~musser/gp/introsort.ps). Volume 27, Issue 8, pp.983–993. August 1997. ISSN:0038-0644.