IntroSort (or introspective sort) is a combined sorting algorithm whose main part is a QuickSort. However for some inputs quicksort degrades to O(n^2) performance which is unacceptable. IntroSort keeps count of the recursions of QuickSort and when it hits a certain threshold, it determines the input is bad and it switches to a HeapSort. Also if the number of the elements is low (usually 16) it uses InsertionSort and also it uses it to sort small partitions created during QuickSort (also usually 16 elelements) because it is faster than further subdividing the partition.

The code here has been changed but most of the credits go to its creator. Unfortunately I do not know his/her name.

(Removed code, it has been changed once posted by some forum script for an unknown reason, download from here - http://filebeam.com/921a9b20e23b8d85b7b80e0e122bed0a)

The hash functions are from Paul Hsieh's site (I hope I'm spelling his name correctly).

I hope this helps.