Quick Sort

In-place partition-based divide & conquer sorting algorithm. Average case O(n log n) with tiny constants, dominating practical workloads. Worst-case O(n^2) occurs only under systematically bad pivot choices. Randomization or median-of-three heuristics make such degeneracy extremely unlikely.

Average

O(n log n)

Worst

O(n^2)

Space

O(log n) stack

Mechanics

Select a pivot element.
Partition elements: values <= pivot before, larger after.
Pivot lands in final position.
Recurse on left/right segments.

Partition Behavior

Partition scanning walks the segment once, expanding a prefix of elements less than or equal to the pivot. Each qualifying element is swapped into the growing prefix. Finally the pivot is swapped into the boundary slot producing two subproblems with the pivot fixed.

Balanced split: ~n/2 | ~n/2 → height ≈ log n

Skewed split: 1 | n-1 → height n

Random pivot: Skew probability decays exponentially

Recurrence & Guarantees

Average / Randomized: T(n) ≈ 2T(n/2) + O(n) → O(n log n).

Worst: T(n) = T(n-1) + O(n) → O(n^2) (pathological pivot chain).

Tail recursion: last call often optimized / manually looped to reduce stack.

Stability: Not stable by default (partition swaps disrupt equal element order).

Practical Speed: Sequential linear scans & in-place operations yield excellent cache utilization.

Heuristics: Median-of-three, ninther, or random pivot reduce variance.

Performance Notes

Switch to insertion sort for tiny (≤16) segments to cut overhead.
Randomization converts adversarial inputs into typical performance.
Three-way partitioning (Dutch flag) handles duplicates efficiently.
Introsort monitors depth & falls back to Heap Sort if degeneration approaches.

View Theory Run Simulation

Merge Sort Binary Search