Merge sort: two ordered streams become one

By UK GCSE Computer Science · independent study · myAudience

Original AI-generated teaching raster via built-in image_gen; author inspected 2026-10-04. · Generated project artwork; no copied exam or publisher illustration. Independent rights/publication review pending.

Merge sort: two ordered streams become one

Merge sort separates ordering into splitting and merging. Split a finite list into smaller halves until each has zero or one item; such lists are already sorted. Recursively sort the halves, then merge them. Entry skills are subroutine parameters, list indexing and bubble sort preservation. Recursion is an implementation technique for this lesson, not a separately claimed GCSE requirement: a function calls itself on a smaller input. The base case is essential to termination. An iterative implementation could use the same split-and-merge idea without Python recursive calls.

Merging assumes both inputs are sorted. Compare their front remaining values, append the smaller to output, and advance only that stream's position. When one stream is exhausted, copy all the other stream's remaining items. The visual merges [2,7,9] and [3,5,8]: take 2,3,5,7,8 through comparisons, then copy 9. Six outputs preserve six inputs. Appending both front items at each comparison may produce 2,3,7,5 and break order. Forgetting the remainder loses data even when the output still looks sorted.

The merge invariant says output is sorted and contains exactly the consumed prefixes of both streams. Every unconsumed value is no smaller than the last output, because each stream is sorted and the smaller front is chosen. Choosing the left value on equality preserves left-before-right tie order. This merge step uses at most a+b-1 comparisons for nonempty streams of lengths a,b, since each comparison consumes one item and the remaining suffix is copied without comparisons. The actual count depends on how the values interleave.

For eight values, splitting has three levels and merging visits all values at each merge level. Under fixed-cost comparisons, index access and appends, the optional time model grows as n log n, whereas bubble sort's worst work grows as n squared. This is an enrichment explanation; formal comparisons are not required by an awarding body. The Python implementation allocates slices and new result lists, so it trades additional memory and copying for reduced worst-case comparisons. Counting merge comparisons alone does not measure all execution costs, and small nearly sorted lists may favour a simpler algorithm.

Test empty lists, odd lengths, duplicates and one-sided remainders. Verify input is preserved and output retains multiplicities. If a sensor stream updates while merging, the sorted precondition can fail; freezing a snapshot is an application responsibility outside the pure function. Splitting does not itself sort anything. A convincing explanation follows a value from original list to a base case and back through merges, showing where order is actually established. The transfer asks for record tie order and a case where an incorrect implementation can seem plausible.

Runnable original Python 3 example (also saved verbatim in examples for CLI execution):
```python
def merge(left, right):
"""Merge sorted comparable sequences into a fresh list; ties take left."""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
return result + left[i:] + right[j:]

def merge_sort(values):
if len(values) <= 1:
return list(values)
middle = len(values) // 2
return merge(merge_sort(values[:middle]), merge_sort(values[middle:]))

assert merge([2, 7, 9], [3, 5, 8]) == [2, 3, 5, 7, 8, 9]
assert merge_sort([7, 2, 2, 1, 9]) == [1, 2, 2, 7, 9]
assert merge_sort([]) == []
```

Worked example: Sort [6,1,4,2] using split and merge mechanics.

Split [6,1] and [4,2], then split each into singletons.

Merge [6] with [1] to [1,6]; merge [4] with [2] to [2,4].

Merge fronts: 1,2,4, then copy remaining 6.

Answer: [1,2,4,6].

Check your understanding: Transfer: a merge routine returns as soon as either stream becomes empty and forgets to copy the other remainder. Give a smallest counterexample with both streams initially nonempty, state the broken property, and explain why testing sortedness alone misses it.

Answer: Merge [1] and [2] would return [1], losing 2. The output remains sorted but is not a permutation of the combined inputs. Assert length 2 and preserved multiplicities, as well as ascending order.

Why: A defect can satisfy one invariant while violating another. “It looks ordered” cannot establish full correctness. Empty-stream tests also expose the bug, but the nonempty example shows how an ordinary merge path reaches the faulty termination.