Merge sort

Divide, sort each half, merge: merging two sorted sequences, the order of the recursive calls, the n log n cost, the auxiliary memory and stability.

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

Merge sort: what is it?
Show the answer
A sort that splits the sequence into two halves, sorts each recursively, then combines the two sorted halves into one sorted sequence.
All the work is in the combining: sorting a one-element sequence costs nothing, and merging two sorted sequences takes a single pass.
At most how many comparisons to merge two sorted sequences of 3 and 5 elements?
- 7
- 8
- 15
- 5
Show the answer
7
Each comparison places one element in the result, except the last remaining element is copied without a comparison: at most 3 + 5 − 1 = 7.
Merge sort sorts the … half, then the … half, and finally … the two results.
Show the answer
Merge sort sorts the left half, then the right half, and finally merges the two results.
The merge only happens once both recursive calls have returned: small sequences are therefore merged before large ones.
Merging two sorted sequences: what is it?
Show the answer
An operation that compares the heads of the two sequences, removes the smaller one into the result, and repeats until one sequence runs out, then copies the rest of the other.
Since each sequence is already sorted, the smallest remaining element is always at the head of one of them: a single pass over n elements is enough, so O(n).