Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Introsort

Sorting Algorithm

Introsort, short for introspective sort, is a hybrid sorting algorithm that combines the fast average performance of quicksort with the guaranteed worst-case performance of heapsort. It begins sorting with quicksort, switches to heapsort when the recursion depth exceeds a bound based on the logarithm of the number of elements being sorted, and switches to insertion sort once a subarray is small enough that insertion sort's low overhead wins out. It was invented by David Musser in 1997. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/

Facts
Time Complexity
Worst-case and average O(n log n). 1
Credited To
David Musser, 1997. 1
Time Complexity
Time Complexity (category)
Linearithmic Time -- O(n log n) 1
Connections

In Field

Algorithms and Complexity Theory, Fields
Source Wikipedia: Introsort
Sources
1. Wikipedia: Introsort
Wikimedia Foundation
  • Lead section
    Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance.
  • Lead section
    Introsort was invented by David Musser in Musser (1997), in which he also introduced introselect, a hybrid selection algorithm based on quickselect (a variant of quicksort), which falls back to median of medians and thus provides worst-case linear complexity, which is optimal.
  • Wikipedia Introsort infobox time O(n log n)
  • In Field: Algorithms and Complexity Theory, Lead sentence
    Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance.
  • In Group: Comparison Sorting Algorithms, Lead
    Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance.
View the Source
Wikidata: Introsort
Wikidata Q1395653, class allow-list match (w-wdresolver-0926)View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.