Quicksort, Heapsort, and Introsort
December 5, 2007 – 10:21 amEver heard of the introspective sort, also known as the introsort algorithm? The Wikipedia page is lacking, but this paper by David Musser describing the algorithm describes it in all its beauty. Basically it is an algorithm that sorts a list of elements by using a combination of Quicksort (with median of 3 and insertion sort enhancements) and Heapsort; Quicksort is used until a certain number of recursions has occured, whereupon the heapsort takes over.
Over the next few days I will present C# implementations of the Quicksort, Heapsort, and Introsort algorithms. In the meantime, go read David Musser’s paper.
One Response to “Quicksort, Heapsort, and Introsort”
This looks interesting and I haven’t ever seen an implementation of introsort. I need to read the Wikipedia article and I will try to read this blog again to catch your next post.
By Sam on Dec 5, 2007