Basic algorithms series: 1. Big-O and O(n²) sorts · 2. Recursion and binary search · 3. Merge sort and quicksort
With a million elements, the O(n²) sorts from part 1 need about 10¹² operations, roughly an hour of work. This post uses divide and conquer (split the problem, solve the pieces with recursion, combine the results) to get down to O(n log n) with merge sort and quicksort. By the end you’ll know which algorithms Arrays.sort/Collections.sort really use and how to avoid the traps of writing a Comparator.
1. Merge sort
Key idea: sort each half, then merge the two sorted halves with two pointers. The heavy lifting is in the merge; in return the running time is always O(n log n) and the sort is stable.
1.1. The idea
- Split the list in two.
- Sort each half recursively. The base case is a range of 0 or 1 elements, which is already sorted.
- Merge the two sorted halves into one.
flowchart TD
A["38 27 43 3 9 82 10"] --> B["38 27 43 3"]
A --> C["9 82 10"]
B --> D["38 27"]
B --> E["43 3"]
C --> F["9 82"]
C --> G["10"]
D --> D2["27 38"]
E --> E2["3 43"]
F --> F2["9 82"]
D2 --> H["3 27 38 43"]
E2 --> H
F2 --> I["9 10 82"]
G --> I
H --> J["3 9 10 27 38 43 82"]
I --> J
1.2. The merge step
Two pointers i and j start at the head of each half. At each step take the smaller element, append it to the output and advance that pointer; when one half runs out, copy the rest of the other. Each element is touched once, so merging n elements costs O(n).
Merging [3, 27, 38, 43] with [9, 10, 82]: take 3, 9, 10, 27, 38, 43; the left half is empty, so copy the remaining 82.
1.3. The code
static void mergeSort(int[] a) {
if (a.length < 2) return;
int[] buf = new int[a.length]; // allocate ONCE, reuse at every level
mergeSort(a, buf, 0, a.length - 1);
}
private static void mergeSort(int[] a, int[] buf, int lo, int hi) {
if (lo >= hi) return; // base case: 0 or 1 element
int mid = (lo + hi) >>> 1;
mergeSort(a, buf, lo, mid);
mergeSort(a, buf, mid + 1, hi);
if (a[mid] <= a[mid + 1]) return; // halves already in order, skip the merge
merge(a, buf, lo, mid, hi);
}
private static void merge(int[] a, int[] buf, int lo, int mid, int hi) {
System.arraycopy(a, lo, buf, lo, hi - lo + 1);
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) {
if (buf[i] <= buf[j]) a[k++] = buf[i++]; // <= (not <) keeps it stable
else a[k++] = buf[j++];
}
while (i <= mid) a[k++] = buf[i++];
while (j <= hi) a[k++] = buf[j++]; // these are already in place, strictly speaking
}
Three details that earn points in an interview:
- Allocate the buffer once. A fresh temp array at every merge generates O(n log n) garbage for the GC.
- Skip the merge when
a[mid] <= a[mid + 1]: an already sorted array costs only O(n). - Compare with
<=so the left element wins ties. That’s what makes merge sort stable (equal elements keep their original order).
1.4. Complexity
T(n) = 2·T(n/2) + c·n: two half-size subproblems plus a linear merge. The recursion tree has log₂ n levels, and at each level the ranges being merged add up to n, so the total is O(n log n).
flowchart TD
L0["Level 0: 1 range of n, merge costs n"] --> L1["Level 1: 2 ranges of n/2, total n"]
L1 --> L2["Level 2: 4 ranges of n/4, total n"]
L2 --> LD["..."]
LD --> LK["Level log n: n ranges of 1 element"]
| Merge sort | |
|---|---|
| Best / average / worst | O(n log n) in all three (the version with the a[mid] <= a[mid+1] check is O(n) on sorted input) |
| Extra memory | O(n) buffer + O(log n) recursion stack |
| Stable | Yes |
| In-place | No (for arrays) |
1.5. Merge sort beyond the textbook
- Linked lists: no random access needed, and merging is just relinking pointers, so no O(n) buffer. The classic example is LeetCode’s “Sort List”.
- Parallelism: the two halves are independent, so they’re easy to sort in parallel;
Arrays.parallelSortbuilds on this (section 4.3).
2. Quicksort
Key idea: pick a pivot, move smaller elements to its left and larger ones to its right, then recurse on both sides. It’s fast and in-place, but bad pivots push it to O(n²), so what you really need to learn is how to defuse the worst case.
2.1. The idea
- Pick a pivot X.
- Partition: smaller than X to the left, larger to the right. X now sits at exactly the position K it will have in the sorted array.
- Recursively sort the part left of K and the part right of K. No merge step needed.
flowchart TD
A["7 2 9 4 3 8 | pivot = 4"] --> P["partition: 2 3 | 4 | 9 7 8"]
P --> L["quickSort(2 3)"]
P --> K["4 is in place"]
P --> R["quickSort(9 7 8)"]
L --> L2["2 3"]
R --> R2["7 8 9"]
2.2. The code: Lomuto partition with a random pivot
Lomuto partition: one pointer scans left to right and pushes every element smaller than the pivot to the front of the range.
static void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}
private static void quickSort(int[] a, int lo, int hi) {
while (lo < hi) {
int p = partition(a, lo, hi);
// recurse into the SMALLER side and loop on the larger one
// -> stack depth is at most O(log n), even with lopsided splits
if (p - lo < hi - p) {
quickSort(a, lo, p - 1);
lo = p + 1;
} else {
quickSort(a, p + 1, hi);
hi = p - 1;
}
}
}
private static int partition(int[] a, int lo, int hi) {
int r = ThreadLocalRandom.current().nextInt(lo, hi + 1);
swap(a, r, hi); // move the random pivot to the end
int pivot = a[hi];
int store = lo; // a[lo..store-1] is always < pivot
for (int i = lo; i < hi; i++) {
if (a[i] < pivot) swap(a, i, store++);
}
swap(a, store, hi); // pivot lands in its final position
return store;
}
private static void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
2.3. Complexity and the worst case
When the pivot splits the array into reasonably balanced parts, there are log n levels of O(n) each: O(n log n) on average, like merge sort. The slides only touch on this, but a senior interview will definitely ask: how do you avoid the worst case?
| Problem | Fix |
|---|---|
| Bad pivots on sorted data | Random pivot (the worst case still exists but becomes vanishingly unlikely) or median-of-three (median of first, middle, last) |
| Lots of duplicates | Three-way partitioning (Dutch national flag): < pivot, = pivot, > pivot; the equal block never needs sorting again |
| O(n) recursion depth on lopsided splits | Recurse into the smaller side, loop on the larger: depth stays ≤ log₂ n |
| An attacker crafting bad input on purpose | Introsort: past a depth of ~2·log n switch to heapsort, guaranteeing O(n log n) |
| Small ranges where recursion overhead dominates | Switch to insertion sort below a few dozen elements |
Hoare partition compared with Lomuto
2.4. Properties
| Quicksort | |
|---|---|
| Average | O(n log n) |
| Worst | O(n²) (introsort: O(n log n)) |
| Extra memory | O(log n) stack when recursing into the smaller side; O(n) if written naively |
| Stable | No |
| In-place | Yes |
3. Comparing sorting algorithms
Key idea: no comparison-based sort beats Ω(n log n) in the worst case. Choosing a sort means choosing between stability, extra memory and how predictable the running time is.
| Algorithm | Best | Average | Worst | Extra memory | Stable | Notes |
|---|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes | Teaching only |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No | Fewest swaps |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes | Great for small / nearly sorted input |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Guaranteed time, external sorting |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Fastest in practice |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Guaranteed and in-place, but cache-unfriendly |
| Counting / Radix | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes | Integer keys in a small range only |
| TimSort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Default for objects in Java and Python |
Why Ω(n log n): there are n! possible orderings and each comparison yields one bit of information, so you need at least log₂(n!) ≈ n log₂ n comparisons. Counting sort and radix sort “beat” this bound because they use the key’s value directly as an array index instead of comparing.
4. How Java really sorts
Key idea: Arrays.sort on primitive arrays uses Dual-Pivot Quicksort; on objects (Arrays.sort(Object[]), Collections.sort, List.sort) it uses TimSort. The reason: primitives don’t need stability, objects do. This is the most valuable part for Java interviews.
4.1. Arrays.sort on primitive arrays: Dual-Pivot Quicksort
- Since Java 7,
Arrays.sort(int[])(andlong[],double[]…) uses Vladimir Yaroslavskiy’s Dual-Pivot Quicksort. It picks two pivotsP1 ≤ P2and splits the array into three parts,< P1,P1..P2and> P2. It beats single-pivot quicksort, mainly because it makes fewer memory reads. - Since Java 14 the worst case is guaranteed O(n log n) (details in the folded block below).
- It’s not stable, but for primitives that doesn’t matter: two
5s are identical, nobody can tell which came first.
Java 14’s rewrite of Dual-Pivot Quicksort
4.2. Arrays.sort(Object[]), Collections.sort, List.sort: TimSort
TimSort (used by Java since Java 7, borrowed from Tim Peters’ Python implementation) is a hybrid of merge sort and insertion sort:
- Scan for runs: stretches that are already ascending (descending ones get reversed).
- Runs shorter than minrun (about 16 to 32 in the JDK; Python uses 32 to 64) are extended with binary insertion sort.
- Merge the runs following rules on a stack that keep merges balanced. When one run keeps “winning”, switch to galloping (exponential search in steps of 1, 2, 4, 8…).
The result: stable, O(n) at best on sorted data, O(n log n) at worst, at most n/2 references of extra memory.
record Order(String customer, int amount) {}
List<Order> orders = new ArrayList<>(List.of(
new Order("bob", 30), new Order("alice", 10),
new Order("bob", 10), new Order("alice", 30)));
orders.sort(Comparator.comparingInt(Order::amount)); // pass 1: by amount
orders.sort(Comparator.comparing(Order::customer)); // pass 2: by customer, stable
// [alice 10, alice 30, bob 10, bob 30]
// cleaner, a single sort with a secondary key:
orders.sort(Comparator.comparing(Order::customer).thenComparingInt(Order::amount));
List.of(...)is immutable, sosortthrowsUnsupportedOperationException; that’s why the example wraps it innew ArrayList<>(...).
4.3. Arrays.parallelSort
It only pays off for large arrays when there are idle cores; inside a web service it competes for resources with the whole application.
The parallel threshold and the ForkJoin common pool
4.4. Comparator traps
4.5. Sort in the database or in the application?
Interactive visualisations
Key idea: entering an array and stepping through every split, merge and partition makes an algorithm stick better than reading code.
- Merge sort: https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/
- Quick sort: https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/visualize/
Exercises
Exercise 1: Live coding “Sort an Array”
Task (paraphrased, LeetCode 912): given an integer array, return it sorted in ascending order without any built-in sort, in O(n log n) time and with as little extra space as possible. Up to 5·10⁴ elements, values in [-5·10⁴, 5·10⁴].
Solutions to Exercise 1: merge sort, three-way quicksort, counting sort
Solution 1: merge sort (code in section 1.3).
public int[] sortArray(int[] nums) {
mergeSort(nums);
return nums;
}
Guaranteed O(n log n), O(n) extra memory. The safest option when the test set deliberately targets worst cases.
Solution 2: three-way quicksort with a random pivot (code in section 2.3).
public int[] sortArray(int[] nums) {
quickSort3Way(nums, 0, nums.length - 1);
return nums;
}
Expected O(n log n), expected O(log n) stack. The tests include sorted arrays and arrays full of duplicates, so a fixed-pivot quicksort or a plain Lomuto partition gets Time Limit Exceeded. That’s precisely the lesson of section 2.3.
Solution 3: counting sort. The value range has only 10⁵ + 1 possible values, so counting frequencies and writing them back is O(n + k):
public int[] sortArray(int[] nums) {
final int OFFSET = 50_000;
int[] count = new int[2 * OFFSET + 1];
for (int x : nums) count[x + OFFSET]++;
int k = 0;
for (int v = 0; v < count.length; v++)
while (count[v]-- > 0) nums[k++] = v - OFFSET;
return nums;
}
I ran merge sort and both quicksorts against 2,000 random arrays (checked against Arrays.sort), a sorted array of a million elements, and a million identical elements.
Exercise 2 (my own): Sorting by multiple keys
Task: given a list of employees (department, salary, name), sort by department ascending, then salary descending within a department, then by name.
Solution to Exercise 2
record Employee(String department, long salary, String name) {}
employees.sort(Comparator.comparing(Employee::department)
.thenComparing(Employee::salary, Comparator.reverseOrder())
.thenComparing(Employee::name, Comparator.nullsLast(Comparator.naturalOrder())));
Remember
- Explain with the recursion tree why merge sort is always O(n log n), and which detail makes it stable.
- List the cases where quicksort degrades to O(n²) and the fix for each.
- Explain the Ω(n log n) lower bound and why counting sort gets around it.
- Know which algorithm
Arrays.sortuses for primitives and for objects, and why they differ. - Spot a dangerous comparator (
a - b, a broken contract,null) and know when to sort in the database instead.
Interview questions
Junior
How does merge sort work, and what’s its complexity?
Split in half, recursively sort each half, merge with two pointers; O(n log n) in every case.
There are log n levels and each level’s merging costs O(n). It needs O(n) extra memory and is stable.
How does quicksort work, and when does it degrade to O(n²)?
Pick a pivot, partition smaller to the left and larger to the right, then recurse on both sides. It degrades to O(n²) when the pivot is repeatedly the min or max.
After partitioning the pivot is in its final spot. Worst-case example: taking the first element as the pivot on a sorted array.
What are the main differences between merge sort and quicksort?
Merge sort divides trivially and does the work when merging; quicksort does the work when partitioning and needs no merge.
Merge sort is stable, guaranteed O(n log n) and uses O(n) memory. Quicksort is in-place and usually faster in practice, but unstable with an O(n²) worst case.
Mid
How do you avoid quicksort’s worst case?
A random pivot or median-of-three, plus introsort to guarantee O(n log n).
- Three-way partitioning when there are many duplicates.
- Recurse into the smaller side to keep the stack at O(log n).
- Like introsort, fall back to heapsort when recursion gets too deep.
Which algorithms do Arrays.sort(int[]) and Arrays.sort(Object[]) use, and why the difference?
Primitives use Dual-Pivot Quicksort, objects use TimSort, because objects need stability and primitives don’t.
Dual-Pivot Quicksort dates from Java 7 and was rewritten in Java 14 with a heapsort fallback. Equal primitives are indistinguishable, so a fast in-place algorithm wins. Objects have several fields and people often sort repeatedly by different keys.
Why is (a, b) -> a - b a dangerous comparator?
The subtraction can overflow, so the comparator returns the wrong sign.
Integer.MIN_VALUE - 1 becomes positive, so the sort comes out wrong or TimSort throws “Comparison method violates its general contract!”. Use Integer.compare or Comparator.comparingInt.
What’s the lower bound for comparison sorting, and how does counting sort get around it?
Ω(n log n); counting sort doesn’t compare but uses key values as indices, reaching O(n + k).
You have to distinguish n! orderings and each comparison gives one bit, so you need log₂(n!) ≈ n log n comparisons. Counting and radix sort only work for integer keys in a small range (or keys that split into digits).
Senior
How does TimSort work, and why does it suit real-world data?
TimSort finds already ordered runs and merges them; real data usually has local order, so it gets close to O(n).
Descending runs get reversed; short runs are extended to minrun with binary insertion sort. Runs are merged according to invariants on a stack so merges stay balanced; when one side keeps winning it switches to galloping. Time-ordered appends or nearly sorted lists run close to O(n), while O(n log n) and stability are still guaranteed.
You need to sort a 100 GB file on a machine with 8 GB of RAM. How?
External merge sort: sort RAM-sized chunks into temp files, then k-way merge them with a min-heap.
- Read ~1 GB chunks, sort each in memory, write it to a temp file (about 100 runs).
- Open every run and keep the head of each in a
PriorityQueue; pop the minimum to the output and refill from the same run. - Use large buffers for sequential I/O. With too many runs, merge in several passes.
It’s also how databases handle an ORDER BY that spills out of sort memory.
What does “Comparison method violates its general contract!” mean, and how do you debug it?
TimSort detected an inconsistent comparator: not antisymmetric, not transitive, or changing results mid-sort.
- Common causes: overflowing subtraction, mishandled
null/NaN, comparing data another thread is mutating, comparators based on time or randomness. - It only surfaces with large enough data, so it’s typically seen in production.
- Fix: build comparators with
Comparator.comparing..., check the contract with property-based tests, sort an immutable snapshot.
The java.util.Arrays.useLegacyMergeSort flag only hides the bug.
Should you use Arrays.parallelSort inside a web service?
Usually not; it runs on the shared ForkJoin common pool, so under heavy load it can raise latency for other requests.
It only pays off for very large arrays (well past the 8192 threshold) when there are idle cores. In a service handling many concurrent requests the cores are already busy, so a sequential sort is often better; batch jobs are a better fit for parallelSort. Always benchmark.
You need the top 100 best-selling products from a stream of 10 million records. Do you sort everything?
No. Keep a min-heap of size 100: O(n log k) time, O(k) memory, and it works on a stream.
For each record, if it beats the heap’s top, replace the top. If the data lives in the database, use ORDER BY sales DESC LIMIT 100 with a suitable index. If everything is already in an array, quickselect gives O(n) on average.
Useful phrases for interviews
- “Both are divide and conquer, but merge sort does the work when combining, while quicksort does it when partitioning.”
- “The recurrence is T of n equals two T of n over two plus n, which solves to n log n.”
- “To guard against the quadratic worst case, I’d pick a random pivot and use three-way partitioning.”
- “I’d recurse into the smaller partition so the stack depth stays logarithmic.”
- “For objects we need a stable sort, which is why Java uses TimSort there.”
- “It depends on the data: if the keys are small integers, counting sort beats any comparison sort.”
- “I’d push the sorting down to the database and let the index do the work.”
- “We don’t need a full sort here; a bounded min-heap gives us the top k in n log k.”
- “That comparator breaks the contract because subtraction can overflow.”
Notes based on the Fundamentals of Backend course (Ronin Engineer), rewritten in my own words.