Introsort

From Algorithmist
Jump to: navigation, 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 O(n\log n).

Reference: Introsort[1]