Introsort

From Algorithmist
Jump to navigation Jump to search
Sorting
Algorithms
Bubble sort
Insertion sort
Selection sort
Quicksort
Merge sort
Heap sort
Introsort
Counting sort
Problems
Problems solvable using sorting
This is a stub or unfinished. Contribute by editing me.

Introsort, or introspective sort is a sorting algorithm that initially uses quicksort, but switches to heap sort if the depth of the recursion is too deep to eliminate the worst-case, and uses insertion sort for small cases because of its good locality of reference.

This algorithm has a worst-case optimal running time of .

Reference: Introsort[1]