IntroSort
Quick sort that switches to heap sort when recursion gets too deep and to insertion sort on small ranges.
More Sorts: Sorted input burns the budget, heap sort rescues
Indices 0 to 10, 11 values, depth budget 6. Big enough and budget left: partition it and recurse on both sides.
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
Before this
Taught by the same lesson
More Sorts covers these too, in the same run.