JAVA-205 · Lesson 4 of 12 · 20 min
Merge sort and quicksort
▶ Video coming soon A video version of this lesson is on the way.
The donated-parts log has grown to 18,400 lines since 2023, one line per part that came in, and Kofi wants it sorted by date and then by code for the annual report. Insertion sort would make about 170 million comparisons in the worst case. On Tuesday, October 5, 2027, Ingrid shows Hamza the two algorithms that bring that down to a few hundred thousand: merge sort and quicksort. Both use the same big idea, which the next two lessons name: split the problem into smaller copies of itself, solve those, and combine the answers.
Merging two sorted lists
Merge sort is built on one simple operation. Given two lists that are each already sorted, you can merge them into one sorted list by repeatedly taking the smaller of the two front elements. Each step makes one comparison and moves one element, so merging lists with a total of n elements takes at most n − 1 comparisons. Kofi does exactly this on paper when he combines the September and October donation sheets, each already in date order.
import java.util.Arrays;
public class Main {
static int comparisons = 0;
static int[] merge(int[] a, int[] b) {
int[] out = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
comparisons++;
if (a[i] <= b[j]) out[k++] = a[i++];
else out[k++] = b[j++];
}
while (i < a.length) out[k++] = a[i++];
while (j < b.length) out[k++] = b[j++];
return out;
}
public static void main(String[] args) {
int[] september = {2, 9, 14, 21, 28};
int[] october = {5, 12, 19, 26};
System.out.println(Arrays.toString(merge(september, october)));
System.out.println("comparisons: " + comparisons);
}
}[2, 5, 9, 12, 14, 19, 21, 26, 28] comparisons: 8
What this code does
The merge keeps an index into each sorted array and copies the smaller front element into the output each time. When one array runs out, the rest of the other is copied without further comparisons. Nine days are merged with eight comparisons, and taking from the first array on ties with less than or equal keeps the merge stable.
Merge sort
Merge sort sorts by splitting the array into two halves, sorting each half by the same method, and merging the two sorted halves. The splitting stops when a piece has one element, because a single element is already sorted. It is a recursive algorithm: the method calls itself on smaller inputs, which lesson 5 explores in detail.
import java.util.Arrays;
public class Main {
static long comparisons = 0;
static void mergeSort(int[] a, int[] tmp, int lo, int hi) {
if (hi - lo < 2) return;
int mid = lo + (hi - lo) / 2;
mergeSort(a, tmp, lo, mid);
mergeSort(a, tmp, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
comparisons++;
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
}
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
System.arraycopy(tmp, lo, a, lo, hi - lo);
}
public static void main(String[] args) {
int[] counts = {14, 9, 22, 6, 9, 3, 17, 1};
mergeSort(counts, new int[counts.length], 0, counts.length);
System.out.println(Arrays.toString(counts) + " with " + comparisons + " comparisons");
java.util.Random rnd = new java.util.Random(2027);
for (int n : new int[] {1_000, 18_400}) {
int[] log = new int[n];
for (int i = 0; i < n; i++) log[i] = rnd.nextInt(1_000_000);
comparisons = 0;
mergeSort(log, new int[n], 0, n);
System.out.println("n = " + n + ": " + comparisons + " comparisons");
}
}
}[1, 3, 6, 9, 9, 14, 17, 22] with 17 comparisons n = 1000: 8679 comparisons n = 18400: 237706 comparisons
What this code does
mergeSort works on the range from lo up to but not including hi, sorts the two halves recursively and merges them through a temporary array. Eight counts take 17 comparisons. For random data seeded with 2027, 18,400 values need about 238,000 comparisons, far fewer than the 170 million insertion sort could need.
Why is merge sort O(n log n)? Look at the levels of the splitting. The array of n elements is split into 2 halves, then 4 quarters, then 8 eighths, until the pieces have size 1, which takes log₂ n levels. At each level, all the merges together handle every one of the n elements once, so each level costs about n comparisons. That is n work at each of log n levels: O(n log n), in the best, average and worst case alike. For 18,400 elements, n log₂ n is about 260,000, which matches the count above.
Merge sort has two more properties worth knowing. It is stable, because the merge takes from the left half on ties. And it is not in-place: the merge needs a temporary array of size n, so it uses O(n) extra memory. Java's TimSort, used for objects, is a refined merge sort that also looks for runs already in order, which is why sorting nearly sorted data with List.sort is so fast.
Quicksort
Quicksort splits differently. It chooses one element as the pivot and partitions the array: everything smaller than the pivot moves to its left, everything larger to its right, and the pivot lands in its final position. Then it sorts the left part and the right part recursively. There is no merge step, because once both sides are sorted the whole array is sorted. Quicksort works in place, needing only the memory for its recursion.
import java.util.Arrays;
public class Main {
static long comparisons = 0;
static int partition(int[] a, int lo, int hi) {
int pivot = a[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
comparisons++;
if (a[j] < pivot) {
int t = a[i]; a[i] = a[j]; a[j] = t;
i++;
}
}
int t = a[i]; a[i] = a[hi]; a[hi] = t;
return i;
}
static void quickSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}
public static void main(String[] args) {
int[] counts = {14, 9, 22, 6, 9, 3, 17, 10};
int[] first = counts.clone();
int p = partition(first, 0, first.length - 1);
System.out.println("after one partition around 10: " + Arrays.toString(first) + ", pivot at " + p);
comparisons = 0;
quickSort(counts, 0, counts.length - 1);
System.out.println(Arrays.toString(counts) + " with " + comparisons + " comparisons");
}
}after one partition around 10: [9, 6, 9, 3, 10, 14, 17, 22], pivot at 4 [3, 6, 9, 9, 10, 14, 17, 22] with 15 comparisons
What this code does
This partition, called the Lomuto scheme, uses the last element as the pivot and moves every smaller element to the front, then swaps the pivot in after them. After one partition around 10, the counts 9, 6, 9 and 3 are to its left and the larger counts to its right, with 10 at index 4. Recursing on the two sides finishes the sort.
Quicksort's best and worst cases
When each pivot splits its range roughly in half, quicksort has the same log n levels as merge sort, with n comparisons per level: O(n log n). On random data it is usually faster than merge sort in practice, because it moves less data and works in place. But if the pivot is always the smallest or largest element, one side of every partition is empty and the other has everything but the pivot. There are then n levels instead of log n, and the comparisons add up to n(n − 1)/2: O(n²). With the last element as pivot, that worst case happens on data that is already sorted, which in real life is common.
public class Main {
static long comparisons = 0;
static java.util.Random rnd = new java.util.Random(7);
static int partition(int[] a, int lo, int hi, boolean randomPivot) {
if (randomPivot) {
int r = lo + rnd.nextInt(hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t;
}
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; j++) {
comparisons++;
if (a[j] < pivot) { int t = a[i]; a[i] = a[j]; a[j] = t; i++; }
}
int t = a[i]; a[i] = a[hi]; a[hi] = t;
return i;
}
static void quickSort(int[] a, int lo, int hi, boolean randomPivot) {
if (lo >= hi) return;
int p = partition(a, lo, hi, randomPivot);
quickSort(a, lo, p - 1, randomPivot);
quickSort(a, p + 1, hi, randomPivot);
}
public static void main(String[] args) {
int n = 2_000;
int[] sorted = new int[n];
for (int i = 0; i < n; i++) sorted[i] = i;
int[] a = sorted.clone();
comparisons = 0;
quickSort(a, 0, n - 1, false);
System.out.println("last-element pivot on sorted input: " + comparisons);
a = sorted.clone();
comparisons = 0;
quickSort(a, 0, n - 1, true);
System.out.println("random pivot on sorted input: " + comparisons);
}
}last-element pivot on sorted input: 1999000 random pivot on sorted input: 26146
What this code does
Sorting 2,000 numbers that are already in order with the last element as pivot makes 1,999,000 comparisons, exactly n(n-1)/2, because every partition peels off just one element. Choosing the pivot at random, here from a Random seeded with 7 so the run is repeatable, brings the count down to 26,146, close to the n log n of about 22,000. A random pivot makes the quadratic case very unlikely whatever the input order.
Real implementations protect against the worst case in several ways: a random pivot, the median of three (the middle value of the first, middle and last elements), switching to insertion sort for small ranges, and recursing on the smaller side first so the stack stays O(log n) deep. Some, called introsort, switch to a heap-based sort if the recursion gets too deep, which guarantees O(n log n). Quicksort is not stable: partitioning swaps elements over long distances.
What Java's sorts actually use
| Call | Algorithm | Stable? | Worst case | Extra memory |
|---|---|---|---|---|
| Arrays.sort(int[]) and other primitive arrays | Dual-pivot quicksort, with insertion sort for small ranges | Not needed: equal ints are identical | O(n log n) in current JDKs | O(log n) stack |
| Arrays.sort(Object[]), List.sort, Collections.sort | TimSort, a merge sort that exploits existing runs | Yes | O(n log n) | Up to O(n) |
| Arrays.parallelSort | Parallel merge of sorted pieces | Yes for objects | O(n log n) | O(n) |
The choice is deliberate. For primitive values stability means nothing, because two equal ints cannot be told apart, so the JDK uses a fast in-place quicksort with two pivots. For objects, stability matters, as JAVA-201 showed when sorting parts in passes, so the JDK uses TimSort. The practical rule is simple: call Arrays.sort or List.sort, choose the order with a Comparator, and write your own sort only to learn or when you have measured a special need.
import java.util.*;
public class Main {
record Donation(String date, String code) {}
public static void main(String[] args) {
List<Donation> log = new ArrayList<>(List.of(
new Donation("2027-09-18", "TUBE-700x25"), new Donation("2027-09-04", "BELL"),
new Donation("2027-09-18", "BELL"), new Donation("2027-09-04", "CHAIN-11"),
new Donation("2027-09-11", "PAD-ROAD")));
log.sort(Comparator.comparing(Donation::date).thenComparing(Donation::code));
for (Donation d : log) System.out.println(d.date() + " " + d.code());
int[] counts = {14, 9, 22, 6, 9, 3};
Arrays.sort(counts);
System.out.println(Arrays.toString(counts));
}
}2027-09-04 BELL 2027-09-04 CHAIN-11 2027-09-11 PAD-ROAD 2027-09-18 BELL 2027-09-18 TUBE-700x25 [3, 6, 9, 9, 14, 22]
What this code does
The donation log is sorted with List.sort, which uses TimSort, by date and then by code, so the two September 4 lines come out BELL then CHAIN-11. Dates written as year-month-day sort correctly as plain text. Arrays.sort on the int array uses dual-pivot quicksort and gives the counts in order.
Try it yourself
Merge two sorted price lists
Two suppliers each send a price list in cents, already sorted from cheapest to dearest. Complete merge so it returns one sorted array containing both lists.
The program should print [450, 600, 899, 1250, 1300, 1999].
import java.util.Arrays;
public class Main {
static int[] merge(int[] a, int[] b) {
int[] out = new int[a.length + b.length];
System.arraycopy(a, 0, out, 0, a.length);
System.arraycopy(b, 0, out, a.length, b.length);
return out;
}
public static void main(String[] args) {
int[] north = {450, 899, 1999};
int[] south = {600, 1250, 1300};
System.out.println(Arrays.toString(merge(north, south)));
}
}Try it yourself
Count a partition
Write partition(int[] a), which uses the last element as the pivot, moves every element smaller than the pivot to the front, puts the pivot right after them, and returns the pivot's final index (the Lomuto scheme).
For {8, 3, 12, 5, 9, 7} the pivot is 7, and the program should print [3, 5, 7, 8, 9, 12] pivot at 2. (For this input one partition happens to leave the whole array sorted.)
import java.util.Arrays;
public class Main {
static int partition(int[] a) {
return a.length - 1;
}
public static void main(String[] args) {
int[] a = {8, 3, 12, 5, 9, 7};
int p = partition(a);
System.out.println(Arrays.toString(a) + " pivot at " + p);
}
}Common mistakes
MistakeChoosing the first or last element as the pivot on data that may already be sorted.
InsteadUse a random pivot or the median of three.
MistakeExpecting quicksort to be stable.
InsteadUse merge sort or List.sort when equal elements must keep their order.
MistakeForgetting that merge sort needs O(n) extra memory.
InsteadAllocate one temporary array and reuse it for every merge.
MistakeWriting a custom sort for ordinary data in production code.
InsteadCall Arrays.sort or List.sort with a Comparator.
MistakeSorting dates written as day/month/year as plain text.
InsteadUse LocalDate, or text in year-month-day order.
Summary and key terms
- Merging two sorted lists takes at most n − 1 comparisons by repeatedly taking the smaller front element.
- Merge sort splits the array in half, sorts each half recursively and merges them; with log n levels of n work each it is O(n log n) in every case, it is stable, and it needs O(n) extra memory.
- Quicksort chooses a pivot, partitions the array so smaller elements are left of the pivot and larger ones right, and sorts the two sides recursively; it works in place and is fast on average, O(n log n), but it is O(n²) when pivots are always extreme, such as the last element of sorted input.
- Random pivots, median of three and switching to insertion sort for small ranges protect it, and it is not stable.
- Java sorts primitive arrays with dual-pivot quicksort and objects with TimSort, a stable merge sort.
- Merge
- Combining two sorted lists into one sorted list.
- Merge sort
- A sort that splits the data in half, sorts the halves recursively and merges them.
- Quicksort
- A sort that partitions around a pivot and sorts the two sides recursively.
- Pivot
- The element quicksort partitions around.
- Partition
- Rearranging a range so smaller elements come before the pivot and larger ones after.
- Lomuto scheme
- A simple partition method that uses the last element as the pivot.
- Median of three
- Choosing as pivot the middle value of the first, middle and last elements.
- TimSort
- The stable, run-aware merge sort Java uses for objects.
- Dual-pivot quicksort
- The quicksort with two pivots that Java uses for primitive arrays.
Practice problems
Work each problem on paper first, then reveal the answer to check.
How many levels of splitting does merge sort make for 1,024 elements?
Show answer
10, since 2¹⁰ = 1,024.
Why is merge sort stable?
Show answer
The merge takes the element from the left half when two are equal.
When does quicksort with a last-element pivot become O(n²)?
Show answer
When the input is already sorted or reverse sorted, so every partition is lopsided.
Why doesn't Arrays.sort(int[]) need to be stable?
Show answer
Equal ints cannot be told apart, so their order does not matter.
What extra memory does merge sort need?
Show answer
A temporary array of n elements, O(n).
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.