#introsort

Introsort

Introsort Introsort, short for introspective sort, is a hybrid sorting algorithm. It starts with quicksort because quicksort is fast in practice. It monitors recursion depth, and when the recursion becomes too deep, it switches to heapsort to avoid quadratic worst case behavior. This gives the practical speed of quicksort with the worst case guarantee of heapsort. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0]...