AlgoScope

IntroSort

Quick sort that switches to heap sort when recursion gets too deep and to insertion sort on small ranges.

Sorting, algorithm, advanced
Range 0 to 10 at depth 6.range 0-101021324354657687981091110

More Sorts: Sorted input burns the budget, heap sort rescues

Decision, step 2 of 77

Indices 0 to 10, 11 values, depth budget 6. Big enough and budget left: partition it and recurse on both sides.

How more sorts works

Cost

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(log n)

Properties

  • Yes: Comparison based
  • No: Stable
  • Yes: In place
  • No: Adaptive
  • No: Online

Taught by the same lesson

More Sorts covers these too, in the same run.