Sedgewick & Wayne · §4.2 Mergesort · lecture slides 32-37

Mergesort: Divide, Sort, Merge

Divide the array into two halves, sort each half recursively, then merge the two sorted halves into a sorted whole. Step through the merge first, then the whole recursion, then see what it costs.

1 · Merge two sorted halves

Both halves of a[lo, hi) are already sorted. Each click on Step moves one entry into the auxiliary array aux[]: the smaller of a[i] and a[j], or what is left when one half is used up. At the end aux[] is copied back.

Halves

a[]

aux[]

left half a[lo, mid) right half a[mid, hi) after the copy-back each entry keeps the color of its half

Code: merge()

What happens

compares0

data moves0

2 · The whole recursion

Each click is one event: a call sort(a, lo, hi) starts, a subarray of size 0 or 1 returns at once, or a call merges its two sorted halves and returns. The call stack shows the calls that are waiting. Next merge jumps to the next merge.

Input

Auto-play speed

left half a[lo, mid) right half a[mid, hi) just merged outside the current call

Code: sort()

Call stack (top = running)

What happens

calls0

depth / max0

merges0

compares0

data moves0

2N lg N-

Trace: the array after each merge

3 · Count the cost, level by level

The calls form levels: one subarray of size N, two of size N/2, four of size N/4, ... Every level moves each entry into aux[] and back: 2N data moves per level, and there are lg N levels. Pick N and count.

Data moves do not depend on the input: always about 2N lg N. Compares do: every merge of n entries makes between n/2 compares (one half runs out first, untouched) and n − 1. Sorted and reversed input give the minimum, about ½ N lg N; random input a bit under N lg N (book, Exercise 4.2.18). When N is not a power of 2, the levels are not all equal, but there are still about lg N of them (Exercise 4.2.19). Insertion sort, for comparison: ~N²/4 compares on random input.

4 · Quadratic against linearithmic

The book calls the gap between N² and N log N the quadratic-linearithmic chasm (p. 553). Predicted time to sort N random 10-letter strings, from doubling tests on one laptop (JDK 17): insertion sort 131 s for 320,000 strings, mergesort 8.5 s for 16 million. Move the slider.

N (number of strings)

1,000,000

insertion

mergesort

The bars are on a log scale, from 1 microsecond to 10,000 years. Predictions use T(N) = c·N² and T(N) = c·N lg N with c fitted to the largest measured run; for small N the real times are lower. Memory runs out long before the largest N: a billion strings need tens of gigabytes.

Companion to the mergesort sessions (lecture CS.11.D; book §4.2, pp. 550–554, Program 4.2.6 on p. 552). Before: insertion sort, the 16 names.