Merge Sort

AQA 4.3.5 — Merge sort

Retrieval: Year 12 Sequence 5's Bubble Sort and Insertion Sort both sort a list in place, one comparison at a time, with O(n²) worst-case performance. Merge sort takes a fundamentally different strategy — divide-and-conquer — and this lesson explains precisely why that strategy achieves genuinely better guaranteed performance.

Key vocabulary

Divide-and-conquer — solving a problem by splitting it into smaller subproblems of the same kind, solving each, then combining the results.
Merge step — combining two already-sorted lists into a single sorted list.

Understand — the divide-and-conquer strategy

Merge sort splits the list in half, recursively sorts each half completely, then merges the two now-sorted halves back into one sorted whole. The recursive splitting continues until a "half" contains just one element — trivially sorted on its own, needing no further work.

See it — implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    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
    result += left[i:]
    result += right[j:]
    return result

Trace it — sorting [5, 3, 8, 1]

Splitting down: [5,3,8,1] → [5,3] and [8,1] → [5],[3] and [8],[1] (all single elements, the base case).

Merging back up: merge([5],[3]) → [3,5]. merge([8],[1]) → [1,8]. merge([3,5],[1,8]): compare 3 and 1 → take 1 → [1]; compare 3 and 8 → take 3 → [1,3]; compare 5 and 8 → take 5 → [1,3,5]; only right remains → append 8 → [1,3,5,8].

Reason about correctness — why merge sort terminates

Every recursive call splits the list roughly in half, and the base case — a list of length 0 or 1 — is reached the moment a "half" can no longer be split meaningfully. Since repeatedly halving any positive list length eventually reaches 1 (exactly Sequence 10's recursion pattern, now applied to list size instead of a counting number), the recursion is guaranteed to reach its base case in a finite number of steps, and therefore guaranteed to terminate.

Reason about correctness — why divide-and-conquer produces a correctly sorted result

This relies on an invariant proven by induction. Base case: a list of 0 or 1 elements is trivially, correctly "sorted" — there's nothing to compare. Inductive step: assume both left and right are already correctly sorted (which the recursive calls guarantee, by the same reasoning applied one level down). The merge step then repeatedly compares the smallest remaining element of each side (always at index i/j, since both sides are sorted) and takes whichever is smaller — this always produces the next-smallest element overall, so the combined result is guaranteed sorted too. Since the base case holds and each level correctly builds on the guaranteed-correct level below it, the whole algorithm is correct for any list length.

Reason about correctness — why the complexity is O(n log n)

Splitting a list of size n in half repeatedly takes log₂(n) levels to reach single elements (exactly the same halving-count reasoning as binary search). At every level of splitting, the total amount of work done by all the merge calls at that level, combined, touches every one of the n elements exactly once — so each level costs O(n). Multiplying the cost per level (O(n)) by the number of levels (O(log n)) gives the total: O(n log n) — genuinely better than Bubble/Insertion Sort's O(n²), because the divide-and-conquer structure avoids ever comparing every element against every other element directly.

Debug it — diagnose, explain, fix, test, justify (incorrect recursion/base condition)

def merge_sort(arr):
    if len(arr) <= 0:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Calling this on almost any list crashes with RecursionError: maximum recursion depth exceeded.

Diagnose: for a list of exactly 1 element, does len(arr) <= 0 become true?
Explain: if the base case is never reached for a single-element list, what does arr[:mid] and arr[mid:] actually produce when mid = 0?
Fix: correct the base-case condition.
Test: confirm the corrected version sorts a small list without error.
Justify: explain, using the "why merge sort terminates" reasoning above, exactly which guarantee this bug breaks.

(len(arr) <= 0 is never true for a 1-element list, so the recursion never stops splitting - a 1-element list gets split into arr[:0]=[] and arr[0:]=[the element], calling merge_sort on the SAME 1-element list again, forever. The fix is len(arr) <= 1. This breaks the termination guarantee directly: the argument relied on eventually reaching a base case that can no longer be split meaningfully, but this version's base case condition is never satisfied by a genuine "can't split further" list.)

Debug it — diagnose, explain, fix, test, justify (incorrect merge logic)

def merge(left, right):
    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

print(merge([1, 3, 5], [2, 8]))

This prints [1, 2, 3, 5] — missing the 8, with no error at all.

Diagnose: what happens to the while loop the moment j reaches len(right) (the shorter list runs out)?
Explain: does the loop's condition allow it to keep copying the remaining elements from the longer list?
Fix: add the missing step to append whatever's left over from either list once the loop ends.
Test: confirm merge([1, 3, 5], [2, 8]) now correctly returns [1, 2, 3, 5, 8].
Justify: explain why this bug silently loses data rather than crashing, and why a quick glance at the output ("it looks sorted!") could easily miss it.

(The while loop stops the moment EITHER list is exhausted, but this version never copies whatever's left in the other, longer list - here, right ([2,8]) empties first (after taking 2), leaving 5 still unprocessed in left, which is simply never appended. The fix adds result += left[i:] and result += right[j:] after the loop, exactly as the working version does. This is dangerous because the output [1, 2, 3, 5] is genuinely sorted, just incomplete - it looks entirely correct unless you specifically check the LENGTH or completeness of the result.)

Common mistake

Assuming merge sort is "always faster" than bubble/insertion sort in every practical sense. For very small lists, the overhead of all the recursive splitting and list-copying can make merge sort's constant factors genuinely slower in practice than a simple insertion sort, even though its worst-case complexity is better — complexity comparisons describe behaviour as n grows large, not a guarantee at every specific size.

Compare, select, justify

A system needs to sort a list of exactly 6 items, and separately needs to sort a list of 100,000 items with no guarantee about how nearly-sorted it already is. Compare insertion sort and merge sort for each case, and justify a choice.

(For 6 items: insertion sort is simpler to implement and its overhead is genuinely lower than merge sort's recursive splitting/merging machinery at such a tiny scale - either would run near-instantly, but insertion sort is the more proportionate choice. For 100,000 items with no guarantee of near-sortedness: merge sort's guaranteed O(n log n) worst case is decisively better than insertion sort's O(n²) worst case, which at this scale could mean roughly 10,000,000,000 comparisons versus merge sort's roughly 1,700,000 - merge sort is clearly justified here.)

Check your understanding

State the time complexity of merge sort, and explain, with reference to the number of levels of splitting, why it is not O(n²) like bubble sort. (4 marks)

(O(n log n). Bubble sort's O(n²) arises because, in the worst case, it may need roughly n passes, each doing up to n comparisons - work proportional to n multiplied by n. Merge sort instead splits the list into log n levels (since halving n repeatedly takes log n steps to reach single elements), and the total work done merging at each level is only O(n), not O(n) repeated n times - multiplying O(n) work per level by log n levels gives O(n log n), which grows significantly more slowly than O(n²) as n increases.)

Challenge

Modify merge so it counts and returns the number of "swaps" (elements taken from the right list while elements still remain in the left list) needed to sort the array — a measure of how far from sorted the original data was.

Looking ahead: the final lesson of this sequence introduces Dijkstra's algorithm — extending BFS's unweighted shortest-path idea to graphs where edges carry a genuine cost.

Learn