Merge sort: stable merge and cost
Goals and prerequisites
Use the existing growth/bounds and insertion/selection-sort lessons. Learn to merge sorted runs, prove the loop invariant, trace duplicate records and derive time and auxiliary space. Arrays are zero-indexed; ranges [l,r) exclude r; comparisons and moves cost O(1).
1. Divide, solve, combine
For a range of length at most one, return. Otherwise m=l+floor((r-l)/2); recursively sort [l,m) and [m,r), then merge them. Recursion creates sorted halves, but concatenating them is insufficient: [2,8] followed by [1,5] is not sorted. The combine step interleaves the halves.
Merge into a separate temporary array B. Set i=l, j=m, k=0. While i<m and j<r, compare A[i] and A[j]; copy the smaller into B[k] and advance that input and k. On equality choose the left input. Append the remaining suffix from either run, then copy B back to A[l:r]. Do not overwrite unread input when using this method.
while i < m and j < r:
if A[i].key <= A[j].key:
B[k] = A[i]; i = i + 1
else:
B[k] = A[j]; j = j + 1
k = k + 1
while i < m: B[k] = A[i]; i = i+1; k = k+1
while j < r: B[k] = A[j]; j = j+1; k = k+1
for t = 0,...,r-l-1: A[l+t] = B[t]2. Invariant and stability
At each main-loop start, B[0:k] is the sorted merge of the consumed prefixes A[l:i] and A[m:j], and contains the k smallest records of the two runs, preserving equal-key order. Both remaining runs are sorted, so their heads contain the next minimum. The chosen record extends the invariant. Initialization has empty consumed prefixes. Termination leaves one run empty; appending the other sorted suffix finishes the merge.
Stability means equal-key records retain their original relative order. If the recursive sorts are stable and a tie chooses the left run, all equal records originally in the left half precede their equal partners in the right half. A tie choosing right can break stability while preserving sorted numeric keys.
Worked merge: left [2a,5,7], right [2b,3,8], where letters identify original records. Comparisons select 2a,2b,3,5,7; then append 8. Output [2a,2b,3,5,7,8] uses five key comparisons. There are six output moves; comparisons and moves are different counts. Merging nonempty runs of lengths p and q uses at most p+q−1 key comparisons, because once one empties the remaining elements need no comparisons.
3. Time and memory
Ordinary merge always processes all n records, so T(n)=2T(n/2)+Θ(n) for powers of two, T(1)=Θ(1). At each of log2 n merge levels total work is Θ(n); therefore best and worst time are Θ(n log n) for this implementation. Already sorted input does not remove merging unless an explicit early-exit optimization is added. Unequal halves for other n preserve this asymptotic bound.
Allocate one reusable buffer of n records and pass its appropriate ranges to calls: auxiliary buffer Θ(n), recursion stack Θ(log n), combined Θ(n). Do not count total allocations across time as simultaneous space. This standard array implementation is not in-place under the O(1)-extra-memory definition. Bottom-up merge sort can eliminate recursion while retaining the buffer. Linked-list variants have different movement/storage details and do not change this array contract.
Exam pitfalls
Stability is not simply sorted output. The split index need not be a pivot value. Merge needs sorted input runs. Include copy-back in linear combine work. The comparison bound is a worst-case bound, not an exact count for every merge.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Stable merge chooses which record on equal keys?
A. Left run B. Right run C. Either always D. Neither
Answer: A
A: Left preserves original cross-half order.
B: Right can reverse equal records.
C: Either does not guarantee stability.
D: A record must be selected.
P02. Maximum key comparisons merging runs of lengths 4 and 5?
A. 4 B. 5 C. 8 D. 9
Answer: C
A: One run may not empty this soon.
B: Both can remain nonempty longer.
C: 4+5−1=8.
D: Last remaining record needs no comparison.
P03. Ordinary array merge sort on already sorted input takes:
A. Θ(1) B. Θ(n) C. Θ(n log n) D. Θ(n²)
Answer: C
A: Every record is processed.
B: There are logarithmically many linear-work levels.
C: All merge levels still run.
D: Balanced splitting avoids quadratic time.
P04. Auxiliary space with reusable buffer and recursive calls?
A. Θ(1) B. Θ(log n) C. Θ(n) D. Θ(n log n)
Answer: C
A: Buffer is not constant.
B: This counts only stack.
C: Linear buffer dominates logarithmic stack.
D: All levels do not need simultaneous separate n-sized buffers.
P05. Merge [1,4] and [2,3] uses how many key comparisons?
A. 1 B. 2 C. 3 D. 4
Answer: C
A: Only selects 1.
B: 2 versus 4 still needs a later comparison with 3.
C: Compare 1:2, 4:2, 4:3; append 4.
D: Appending 4 requires no key comparison.
P06. What must be true before a merge starts?
A. All keys distinct B. Both input runs sorted C. Left maximum below right minimum D. Equal run lengths
Answer: B
A: Duplicates are allowed.
B: Sorted heads let us choose the next global minimum.
C: That is a special easy case, not a requirement.
D: Unequal runs can be merged.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in