Sorting Algorithms

Every common sort at a glance — time, space, stability, and which one to reach for.

Comparison sorts

Quicksort: best/avg O(n log n) · worst O(n²) · space O(log n) · not stable · in-place
Merge sort: O(n log n) always · space O(n) · stable
Heap sort: O(n log n) always · space O(1) · not stable · in-place
Insertion sort: best O(n) · avg/worst O(n²) · space O(1) · stable
Selection sort: O(n²) always · space O(1) · not stable
Bubble sort: best O(n) · avg/worst O(n²) · space O(1) · stable

Counting sort: O(n + k) · space O(k) · stable — small integer key range k
Radix sort: O(n·k) for k digits · space O(n + k) · stable — fixed-width integers/strings
Bucket sort: avg O(n + k) · worst O(n²) · space O(n + k) · stable — uniformly spread values

Nearly sorted / tiny n: Insertion sort — near O(n), low overhead
Need stability: Merge sort (or a stable library sort)
Fast average, in-place: Quicksort — but guard against the O(n²) worst case
Guaranteed O(n log n): Heap (O(1) space) or merge (stable)
Small integer range: Counting / radix — linear, skips comparisons
Uniform real values: Bucket sort — scatter, sort each, concatenate

Comparison lower bound: Any comparison sort needs Ω(n log n) in the worst case
Stable: Equal keys keep their original relative order
In-place: Uses O(1) (or O(log n)) extra space beyond the input
Non-comparison: Uses key structure (digits, counts) to beat n log n — needs bounded keys