Introsort
From Algorithmist
| 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(nlogn).
