Quick Sort Theory

Quick Sort partitions the array in-place around a pivot establishing two subproblems separated by the pivot's final position. Average behavior yields O(n log n) work due to near-balanced splits in expectation; worst-case O(n^2) arises only with persistently extreme pivot placements.

Recurrence & Partitioning

General: T(n) = T(k) + T(n-k-1) + O(n) where k is pivot final index shift.

Average / Random: Expected k ≈ n/2 → T(n) ≈ 2T(n/2)+O(n) → O(n log n).

Worst: k ∈ {0, n-1} repeatedly → T(n)=T(n-1)+O(n)=O(n^2).

Depth: Balanced height ≈ log n; degenerate height n.

Partition Scan: Maintains boundary i of ≤ pivot region; scans j and swaps qualifying elements forward.

Cost per Level: Each level touches every element once → O(n) work per level.

Randomization: Probability of ≥90% skew repeatedly shrinks exponentially.

Pseudocode

1function quickSort(arr, lo, hi):
2  if lo >= hi: return
3  p = partition(arr, lo, hi)
4  quickSort(arr, lo, p-1)
5  quickSort(arr, p+1, hi)

Complexity & Properties

Best

O(n log n)

Average

O(n log n)

Worst

O(n^2)

Space

O(log n) expected

In-Place

Yes (stack aside)

Stable

Cache friendly sequential partition sweeps.
Tail call elimination reduces stack usage on one side.
Introspective hybrids cap worst-case by switching when depth > 2 log n.

Practical Notes

Median-of-three reduces vulnerability to presorted inputs.
Three-way partitioning improves duplicate-heavy datasets.
Switching to insertion sort for small segments lowers constant factors.

Merge Sort Run Simulation Binary Search