Sorting is the workhorse of algorithms: it is the preprocessing step that turns hard problems (deduplication, nearest-pair, interval merging, two-sum-on-sorted) into easy ones, and it is the canonical place interviewers probe your grasp of time/space trade-offs.
Comparison vs non-comparison sorts
A comparison sort only ever asks "is a before b?" via a comparator. Any such sort must make at least Ω(n log n) comparisons in the worst case — the decision tree distinguishing n! permutations has height log₂(n!) ≈ n log n. QuickSort, MergeSort, HeapSort, and Timsort all live here.
Non-comparison sorts break the bound by exploiting structure in the keys: CountingSort, RadixSort, and BucketSort read the digits/values directly and run in O(n + k) or O(d·n). They only apply when keys are bounded small integers (or decompose into bounded digits).
Two properties that matter
- Stable — equal elements keep their original relative order. Essential when sorting by one field after another (sort by name, then stably by department). MergeSort, Timsort, and CountingSort are stable; QuickSort and HeapSort are not.
- In-place — O(1) (or O(log n) stack) auxiliary space. QuickSort and HeapSort are in-place; MergeSort and Timsort need O(n) scratch.
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| QuickSort | O(n log n) | O(n log n) | O(n²) | in-place, unstable |
| MergeSort | O(n log n) | O(n log n) | O(n log n) | O(n) space, stable |
| HeapSort | O(n log n) | O(n log n) | O(n log n) | in-place, unstable |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) space, stable, adaptive |
| CountingSort | O(n + k) | O(n + k) | O(n + k) | non-comparison, stable |
What Java actually does
Arrays.sort(int[])and other primitives use a dual-pivot QuickSort (Vladimir Yaroslavskiy's variant). Primitives have no notion of "identity beyond value," so stability is irrelevant — and the in-place, cache-friendly quicksort wins on speed.Arrays.sort(Object[])andCollections.sort(List)use Timsort (an adaptive MergeSort). Objects need a stable sort because two objects that compare equal may still be distinguishable, and developers rely on stable behavior for multi-key sorts.Collections.sortsimply delegates tolist.sort(c), which copies to an array and runs Timsort.