Preview

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

Merge sorting

Merge sort divides a list repeatedly until each sublist contains one item, then merges sorted sublists back together in order. OCR expects you to understand and apply the steps and recognise the algorithm, not memorise implementation code.

Multiple choice1 mark

What happens after merge sort has split the data into single-item sublists?

ASorted sublists are merged into larger sorted sublists
BThe values are searched linearly
COnly adjacent values are swapped
DThe original list is abandoned

Split, then merge in order

For [8, 3, 6, 2]:

Split to [8, 3] and [6, 2], then to [8] [3] [6] [2].
Merge [8] and [3] as [3, 8].
Merge [6] and [2] as [2, 6].
Merge [3, 8] and [2, 6] by repeatedly taking the smaller front value, producing [2, 3, 6, 8].

The merge step does not simply append one unsorted group to another and sort it later.

Multiple choice1 mark

Which is the correct merge of sorted lists [2, 7, 9] and [3, 5, 10]?

A[2, 7, 9, 3, 5, 10]
B[2, 3, 5, 7, 9, 10]
C[10, 9, 7, 5, 3, 2]
D[3, 5, 10, 2, 7, 9]

Worked example: the merge operation

Run the function below to see how two already-sorted lists are combined. The two index variables identify the next unmerged value in each list. The smaller value is appended, and only that list's index moves forward.

When one list has no values remaining, the final statement adds the untouched remainder of the other list.

Worked example

def merge(left, right):
    result = []
    left_index = 0
    right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index = left_index + 1
        else:
            result.append(right[right_index])
            right_index = right_index + 1
    result = result + left[left_index:] + right[right_index:]
    return result

print(merge([2, 7, 9], [3, 5, 10]))

Written answer6 marks

Apply merge sort to [7, 1, 6, 4]. Show the single-item sublists, the two sorted two-item sublists and the final sorted list.

Show both the splitting and merging stages.

Students type their answer here.

Programming challenge: merge two sorted lists

The two supplied lists are already sorted. Build merged by repeatedly comparing the next unmerged value from each list and appending the smaller one. When one list is exhausted, append the remaining values from the other.

This challenge makes the merge stage concrete; OCR does not require you to memorise this implementation. Focus on preserving sorted order and including every value exactly once.

Coding task3 marks

# Merge these two already-sorted lists into one sorted list.
left = [1, 6, 11]
right = [3, 4, 12]
merged = []
# Write code that builds merged in ascending order.

Multiple choice1 mark

Which feature most clearly identifies merge sort in an algorithm?

AA sorted search area is halved around a target
BAdjacent values are swapped on repeated passes
CThe data is split into sublists and sorted sublists are combined
DItems are checked from index zero

Written answer3 marks

Correct this claim: 'Merge sort joins the sublists in any order and sorts the completed list at the end.'

Explain what must be true of sublists during merging and how the next value is chosen.

Students type their answer here.

Review

Merge sort first divides the data to single-item sublists, then repeatedly merges already-sorted sublists. During a merge, compare the next unused values and take the smaller one. Show both splitting and merging when an exam question asks you to apply the complete algorithm.