python-programming / searching-and-sorting · Lesson 26

Lesson 26 — Searching and sorting

Merge Sort

Divide data into smaller lists, then merge sorted lists back together.

Merge sort has two key ideas: repeatedly divide the data until the pieces contain single items, then merge the pieces back together in sorted order.

Predict

Read the code first. Do not run it yet.

merge-sort-predict.py

left = [3, 8]
right = [4, 7]
result = [0, 0, 0, 0]
i = 0
j = 0
k = 0

while i < len(left) and j < len(right):
    if left[i] < right[j]:
        result[k] = left[i]
        i = i + 1
    else:
        result[k] = right[j]
        j = j + 1
    k = k + 1
print(result, i, j, k)

Predict before running

Which values are copied into result first?
When does the loop stop?
What do the index variables i, j and k track?

Investigate

Use this code to explain exactly how the program works.

merge-sort-investigate.py

data = [38, 27, 43, 3]
print([38, 27], [43, 3])
print([38], [27], [43], [3])
print([27, 38], [3, 43])
print([3, 27, 38, 43])

Investigate the code

Identify the divide stages.
Identify the merge stages.
During merging, why must the smaller front value be chosen first?

The merge-sort process

How it works

Divide the original list into smaller sublists.
Continue until each sublist contains one item.
Merge neighbouring sublists by repeatedly taking the smaller front item.
Continue merging until one sorted list remains.

Merging two sorted lists

merge.py

left = [3, 8, 12]
right = [4, 7, 15]
result = [0] * (len(left) + len(right))
i = 0
j = 0
k = 0

while i < len(left) and j < len(right):
    if left[i] < right[j]:
        result[k] = left[i]
        i = i + 1
    else:
        result[k] = right[j]
        j = j + 1
    k = k + 1

while i < len(left):
    result[k] = left[i]
    i = i + 1
    k = k + 1

while j < len(right):
    result[k] = right[j]
    j = j + 1
    k = k + 1

print(result)

Output

[3, 4, 7, 8, 12, 15]

No recursion is needed to understand the algorithmThe essential skill is tracing the divide and merge stages. A full program can be implemented in different ways.

Understand the stepsFocus on recognising and applying divide-then-merge behaviour rather than memorising one implementation.

Recognise and apply the algorithmBe able to follow these characteristic steps on a data set and recognise the algorithm from program code. Correct implementations can use different variable names or loop structures, so focus on the behaviour rather than memorising one exact version.

Self-study guide

Merge sort follows a divide-and-merge strategy. The data is repeatedly split into smaller sections until single-item sections remain. Those already-sorted sections are then merged back together in sorted order.

OCR expects you to understand the main steps, apply the algorithm to a data set, identify it from code/ERL and understand code segments. You are not required to memorise a long recursive implementation or a complete merge routine.

OCR focusUnderstand the split stages and especially how two already-sorted sections are merged. Be able to apply merge sort on paper and recognise merge code.

OCR Exam Reference Language ↔ Python

OCR Exam Reference Language / term	Python	What to remember
`Merge sort`	`split → merge stages`	The high-level algorithm is language-independent.
`split until single items`	`conceptual sublists`	Single-item sections are already sorted.
`merge sorted sections`	`compare next unused values`	Copy the smaller next item, then advance on that side.
`not required: memorise full code`	`use supplied/recognisable segments`	OCR explicitly says the code/ERL need not be remembered.

Read both formsIn an examination you may see OCR Exam Reference Language even when you have learned the idea in Python. Translate the structure, not just the symbols.

Worked example

The merge step is the heart of the algorithm. Both inputs must already be sorted.

lesson-26-worked.py

left = [2, 7, 11]
right = [3, 5, 9]
result = [0, 0, 0, 0, 0, 0]

left_index = 0
right_index = 0
result_index = 0

while left_index < len(left) and right_index < len(right):
    if left[left_index] < right[right_index]:
        result[result_index] = left[left_index]
        left_index = left_index + 1
    else:
        result[result_index] = right[right_index]
        right_index = right_index + 1

    result_index = result_index + 1

while left_index < len(left):
    result[result_index] = left[left_index]
    left_index = left_index + 1
    result_index = result_index + 1

while right_index < len(right):
    result[result_index] = right[right_index]
    right_index = right_index + 1
    result_index = result_index + 1

print(result)

Output

[2, 3, 5, 7, 9, 11]

Work through it line by line

Compare the first unused items: 2 and 3. Copy 2.
Compare 7 and 3. Copy 3.
Compare 7 and 5. Copy 5.
Continue until one input section is exhausted.
Any values remaining on the other side are already in order, so copy them directly.

Another example

At GCSE level, you should also be comfortable showing the merge stages without writing the merge routine from scratch.

lesson-26-example-2.py

# Values: 9, 2, 6, 1
# Split: [9, 2] [6, 1]
# Split: [9] [2] [6] [1]
# Merge: [2, 9] [1, 6]
# Merge: [1, 2, 6, 9]

Why this example matters

The original data is divided until single-item sections remain.
Each pair is merged into sorted order.
The two sorted pairs are merged to form the final sorted list.

Common mistakes

Avoid these errors

Thinking the two inputs to a merge can be unsorted.
Treating merge sort as repeated adjacent swapping.
Believing OCR requires memorisation of a complete recursive program.
Losing duplicate values during a merge; duplicates must be preserved.

Exam-safe warningThe syllabus explicitly says you do not need to remember the code/ERL for the standard searching and sorting algorithms. Understand the steps and code segments instead.

Exam-ready checklist

You should now be able to

Show the split and merge stages for a data set.
Merge two already-sorted sections correctly.
Identify merge sort from code/ERL.
Explain why single-item sections are already sorted.
State that full code memorisation is not required.

What you have learned

Merge sort divides data into smaller sublists.
Single-item lists are already sorted.
Sorted sublists are merged by repeatedly choosing the smaller next item.
Merging continues until one sorted list remains.