- Introsort
Introsort or introspective sort is a
sorting algorithm designed byDavid Musser in 1997. It begins withquicksort and switches toheapsort when the recursion depth exceeds a level based on (thelogarithm 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 arecomparison sort s, it too is a comparison sort.In quicksort, one of the critical operations is choosing the pivot: the element around which the list is partitioned. The simplest pivot selection algorithm is to take the first or the last element of the list as the pivot, causing poor behavior for the case of sorted or nearly-sorted input.
Niklaus Wirth 's variant uses the middle element to prevent these occurrences, degenerating to O("n"²) for contrived sequences. The median-of-3 pivot selection algorithm takes the median of the first, middle, and last elements of the list; however, even though this performs well on many real-world inputs, it is still possible to contrive a "median-of-3 killer" list that will cause dramatic slowdown of a quicksort based on this pivot selection technique. Such inputs could potentially be exploited by an aggressor, for example by sending such a list to an Internet server for sorting as adenial of service attack.Musser reported that on a median-of-3 killer sequence of 100,000 elements, introsort's running time was 1/200 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.Similarly, Musser also introduced a worst-case linear
selection algorithm with time comparable to that of "Hoare's algorithm", a simple adaptation of quicksort that is the most efficient selection algorithm used in practice. This is called introspection selection or Introselect.The June 2000 SGI C++
Standard Template Library [http://www.sgi.com/tech/stl/stl_algo.h 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.References
* cite journal
last=Musser
first=David
title=Introspective Sorting and Selection Algorithms
url=http://www.cs.rpi.edu/~musser/gp/introsort.ps
doi=10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#
journal=Software: Practice and Experience
volume=27
issue=8
publisher=Wiley
year=1997
pages=983–993* Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.
External links
* [http://ralphunden.net/content/tutorials/a-guide-to-introsort/ "A guide to Introsort"] Paper created over the course of a student research project by Ralph Unden. Contains a complete implementation in Java.
Wikimedia Foundation. 2010.
