Introsort

Introsort (introspective sort) is a hybrid sorting algorithm invented by David Musser in 1997 that combines the average-case speed of Quicksort with the guaranteed O(n log n) worst-case bound of heapsort. It begins as quicksort but monitors the recursion depth; if the partitioning becomes unbalanced beyond a threshold, it switches to heapsort to prevent the quadratic worst case. Most standard library implementations of sort() in C++ and other languages use introsort or its variants.

Introsort is not merely a pragmatic hack. It is a formal acknowledgment that the efficiency-robustness tradeoff cannot be resolved within a single algorithmic framework. Quicksort is efficient; heapsort is robust. Introsort delegates between them based on runtime conditions, creating a meta-algorithm that adapts its own structure to the input's adversarial potential. The question it raises — whether all robust systems must eventually become systems of systems — remains unresolved.