Community resourceWorksheet

OCR H446 2.3.1 Merge sort

Part 7 of 16 · H446 2.3.1 · Algorithms

Merge sort is the H446 2.3.1 divide-and-conquer example, and the difficulty is rarely the splitting; it is the merge loop, where students lose track of which values have been consumed. This worksheet makes both the recursive structure and every merge-loop state visible before asking for an implementation and a memory trade-off judgement.

Students will:

  • model the recursive split down to base cases and the combination back up
  • show the complete split and merge states for a small list by hand
  • trace a merge loop index by index, including the condition that ends it
  • implement splitting and merging so no unconsumed value is lost
  • explain the predictable scaling of merge sort against its extra memory demand

Inside: 5 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 2 written answers, 1 Python task and 1 trace table. 26 marks, about 25 to 40 minutes.

Series: H446 2.3.1 · Algorithms, part 7 of 16.

Shared by Coding PathwayVerified teacher

  • 11 cells
  • About 30 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Merge sort

Merge sort is divide and conquer: split to base cases, then combine sorted results.

By the end, you will be able to

  • model recursive splitting and merging;
  • merge two sorted sequences correctly;
  • read, trace and write merge sort;
  • evaluate O(n log n) time and auxiliary-space trade-offs.

Reactivate: recursion needs a base case and progress toward it.

Split, solve, combine

Merge sort split and merge[8, 3, 6, 2, 7, 1, 5, 4][8, 3, 6, 2][7, 1, 5, 4][1, 2, 3, 4, 5, 6, 7, 8]recursively reach single-item base cases; merge two sorted halves

During merge, compare the first remaining item of each sorted half, take the smaller, and when one half empties append the remainder. Comparing arbitrary internal items breaks the invariant.

Multiple choice1 mark

What is the natural merge-sort base case?

  • AA list with an even length
  • BA list containing its maximum
  • CA list of length zero or one
  • DA list already split once
Written answer6 marks

Show the complete split and merge states for [6, 3, 8, 2].

Include all single-item base cases and comparison-led merges.

Students type their answer here.

Trace table5 marks

Trace every iteration of this merge loop. Record i, j, the condition result, the comparison used and merged after each append, including the false condition that ends the loop and the appended remaining item.

Enter a value only when it changes. Record output in order.

Use one row for each pass through the loop. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython
  1. left = [2, 6]
  2. right = [3, 8]
  3. i = 0
  4. j = 0
  5. merged = []
  6. while i < len(left) and j < len(right):
  7. if left[i] <= right[j]:
  8. merged.append(left[i])
  9. i = i + 1
  10. else:
  11. merged.append(right[j])
  12. j = j + 1
  13. merged.append(right[j])
  14. print(merged)
Trace table with 8 columns
Rowleftrightijmergedi < len(left) and j < len(right)left[i] <= right[j]Output
1
2
3
4
5
6
7

Worked implementation structure

merge_sort calls itself on left and right halves, then calls merge. The merge loop consumes indexes without losing unconsumed values. A solution may use slicing or index ranges; state the extra-space consequence.

Coding task10 marks
def merge(left, right):
    pass

def merge_sort(data):
    pass
Written answer5 marks

Explain why merge sort scales predictably but often needs more auxiliary memory than an in-place insertion sort.

Use recursion levels, merging and copied/result storage.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks4 marks
Merge sort first completion 1 the data into smaller parts. A list of length zero or one is a completion 2. Two ordered halves are combined by a completion 3 step. Temporary result lists contribute completion 4 space.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.