Introsort

Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to Heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. It is the best of both worlds, with a worst-case O(n log n) runtime and practical performance comparable to quicksort on typical data sets. Since both algorithms it uses are comparison sorts, it too is a comparison sort.