This combines the good parts of the three algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort.
If a heapsort implementation and partitioning functions of the type discussed in the quicksort article are available, the introsort can be described succinctly as The factor 2 in the maximum depth is arbitrary; it can be tuned for practical performance.
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.
The June 2000 SGI C++ Standard Template Library 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 Knuth final insertion sort pass for partitions smaller than 16.
The GNU Standard C++ library is similar: uses introsort with a maximum depth of 2×log2 n, followed by an insertion sort on partitions smaller than 16.
[2] LLVM libc++ also uses introsort with a maximum depth of 2×log2 n, however the size limit for insertion sort is different for different data types (30 if swaps are trivial, 6 otherwise).