Sorting Essentials
Merge sort and quicksort at a glance, why Java uses each, stability, and the times when sorting first is the whole solution.
On this page
You'll rarely implement a sort from scratch in a real job - Arrays.sort and Collections.sort are
right there - but interviewers expect you to understand how the major algorithms work, their trade-offs,
and, crucially, to recognize when sorting first makes an otherwise hard problem easy.
The two you must know: merge sort and quicksort
Merge sort splits the array in half, recursively sorts each half, and merges the two sorted halves. It's always O(n log n), stable, but needs O(n) extra space for merging:
// merge sort — O(n log n) time, O(n) space, stable
void mergeSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid); // sort left
mergeSort(a, mid + 1, hi); // sort right
merge(a, lo, mid, hi); // combine two sorted halves
}Quicksort picks a pivot, partitions elements into "less than pivot" and "greater than pivot," and recurses on each side. It's O(n log n) average but O(n²) worst case (bad pivots), and sorts in place with O(log n) stack space. Its partition step is also the basis of quickselect (next lesson).
| Merge sort | Quicksort | |
|---|---|---|
| Time | O(n log n) always | O(n log n) avg, O(n²) worst |
| Space | O(n) | O(log n) in place |
| Stable? | Yes | No |
What Java actually uses
Arrays.sort on primitives uses a dual-pivot quicksort (fast, in place, stability doesn't matter
for primitives). On objects, it uses Timsort - a stable, adaptive merge sort that exploits
existing runs and is O(n log n) worst case. Knowing this - primitives get quicksort, objects get a
stable merge sort - is a strong interview detail.
The real lesson: sort first, then the problem is easy
Often the winning move is simply sort, then solve. Sorting is O(n log n); if it turns an O(n²) problem into an O(n) scan afterward, that's a huge win:
- Two-sum / three-sum → sort, then two pointers.
- Merge intervals → sort by start, then sweep.
- Find duplicates / closest pair → sort, then compare adjacent.
// merge overlapping intervals — sort by start, then sweep
Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
List<int[]> merged = new ArrayList<>();
for (int[] iv : intervals) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < iv[0])
merged.add(iv); // no overlap
else
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], iv[1]);
}Stability matters when there's a secondary order
A sort is stable if it preserves the relative order of equal elements. It matters when you sort by one key but want ties broken by a prior order - e.g. sort employees by department while keeping alphabetical order within each. Timsort (Java's object sort) is stable; primitive quicksort is not (but primitives have no identity, so it's moot).
Faced with a pile of a thousand unsorted invoices and asked repeatedly 'is there one for client X?', you don't rummage the whole pile each time (O(n) per query). You spend one upfront effort alphabetizing them (O(n log n)), and then every lookup is a quick flip to the right section. Sorting first is that upfront investment: a single O(n log n) pass that makes the actual problem - pairing, deduping, merging, searching - trivially fast afterward.
For each scenario, pick merge sort or quicksort and justify: (a) you must sort a linked list; (b) you're sorting objects and must preserve the order of equal elements; (c) memory is extremely tight and the data is a primitive array.
Which sorting algorithm does Java's Arrays.sort use for an array of objects, and why?
Key takeaways
- Merge sort is O(n log n) always, stable, but O(n) space; quicksort is O(n log n) average, in place, but O(n^2) worst and unstable.
- Java sorts primitives with dual-pivot quicksort (in place) and objects with Timsort (stable merge, O(n log n) worst case).
- Stability preserves the order of equal elements - important when a secondary ordering matters.
- Often the whole solution is 'sort first, then solve': two-sum via two pointers, merge intervals, dedupe adjacent.
- Sorting's O(n log n) cost is worth it when it turns an O(n^2) problem into an O(n) scan.