OCR H446 algorithms / AQA 7517 algorithms
Use divide and conquer to implement merge sort without calling sorted() or list.sort().
Merge sort divides a list into smaller sections, sorts those sections and merges them in order. The algorithm has O(n log n) time complexity in standard implementations. Trace how two sorted halves are combined without losing items.
Watch out: The merge step must copy all remaining items after one half has been exhausted.
Study this example, identify inputs and outputs, then trace the key variables. Run and adapt it in Python 3.
def merge_sort(values):
if len(values) <= 1: return values[:]
mid = len(values)//2
left, right = merge_sort(values[:mid]), merge_sort(values[mid:])
output=[]; i=j=0
while i<len(left) and j<len(right):
if left[i] <= right[j]: output.append(left[i]); i+=1
else: output.append(right[j]); j+=1
return output + left[i:] + right[j:]
Use divide and conquer to implement merge sort without calling sorted() or list.sort(). Download the starter, design your solution, and add tests before revealing the answer.
Download starter + solution ZIP ↓
Stretch task: investigate time/space complexity or data validation, then write an evaluation of your approach.
def merge_sort(values):
if len(values) <= 1: return values[:]
mid = len(values)//2
left, right = merge_sort(values[:mid]), merge_sort(values[mid:])
output=[]; i=j=0
while i<len(left) and j<len(right):
if left[i] <= right[j]: output.append(left[i]); i+=1
else: output.append(right[j]); j+=1
return output + left[i:] + right[j:]
assert merge_sort([7, 2, 9, 1, 4, 4]) == [1, 2, 4, 4, 7, 9]
print(merge_sort([7, 2, 9, 1, 4]))
Change one boundary condition in the starter or reference program. Predict which test fails, then repair it and document why.
Concept check: What is merge sort’s time complexity in the general case?
O(n log n), because the data is split logarithmically and merged linearly at each level.
Describe the algorithm or design in your own words; include a normal test, a boundary test and an invalid input. Compare your answers with the reference solution and record one improvement.
Progress is stored only in this browser.
Want extra practice? Try interactive Python tracing and debugging questions →
Split the list until sublists have one element, then trace each merge with two pointers. Consider time complexity and the additional storage needed rather than memorising only the algorithm name.
Check: O(n log n).