🗺️Mappedia

QuickSort Optimizations

Performance improvements include switching to Insertion Sort for small subarrays, tail recursion elimination, and three-way QuickSort for arrays with duplicates. Introsort switches to HeapSort for recursion depth > 2log(n) to guarantee O(n log n)

Article body and graph labels may still appear in Russian where English translations have not been added yet.

📖6 min read📊Level 7🗺️2 subtopics📅April 16, 2026

Аркадий Павлович Бессмертный

Author: Бессмертный А.П.

Loading map...

Introsort
Introsort = QuickSort + HeapSort. If recursion depth > 2·log n (degrades to O(n²)), switches to HeapSort (guarantees O(n log n)). Used in std::sort (C++), Array.sort (Java). Musser (1997). Best of both worlds: QuickSort speed + HeapSort reliability.
Tail Recursion in QuickSort
Optimizes stack depth: after sorting the smaller part, recursively sort the larger part via a loop (tail call). Stack depth O(log n) instead of O(n) in the worst case. Compilers with tail call optimization (TCO) convert to iteration. Important for large arrays.

Оптимизации QuickSort

❓Часто задаваемые вопросы

Оптимизации QuickSort — это тема о правилах, механизмах и практиках в своей области. Она помогает понять, как принимаются решения и к каким последствиям они приводят.

🔗Learn more

YouTube

What is QuickSort Optimizations?QuickSort Optimizations: lecture QuickSort Optimizations: overview