Merge sort

Standard sorting algorithms: Merge sort

2.1.3 Searching and sorting algorithms

Searching and sorting algorithms — Note 4 of 5

Understand the main steps of each algorithm, Understand any pre-requisites of an algorithm, Apply the algorithm to a data set, Identify an algorithm if given the code or pseudocode for it

What you need to know

Merge sort is a divide-and-conquer sorting algorithm. It works by continuously splitting the list in half until each sublist contains just one item, then merging those sublists back together in the correct order. It is faster than bubble sort for large datasets but uses more memory due to the temporary sublists created during the process.

What to know

Divide: keep splitting the list in half until each sublist has only ONE element.
Conquer (merge): compare elements from the sublists and merge them back in SORTED ORDER.
The MERGING process itself produces the sorted order — there is NO separate sorting step after merging.
Example: [45,12,-99,100,-13,0,17,-27] → split to individuals → merge into sorted pairs [12,45],[-99,100],[-13,0],[-27,17] → merge into sorted fours [-99,12,45,100],[-27,-13,0,17] → final sorted list.
Uses a divide-and-conquer approach — very efficient for large datasets.
Faster than bubble sort and insertion sort for large lists.
Uses more memory because it creates temporary sublists during the splitting and merging process.
More complex to implement than bubble sort.
The algorithm is recursive: it calls itself on each half of the list.
Merge sort is the sorting algorithm that 'splits data into individual items before recombining in order'.

Exam technique

Mistake:Merging unsorted groups and then sorting them afterwards is WRONG. Each merge step produces a correctly ordered list.

Code examples

Merge sort in Python

python

def merge_sort(data):
    if len(data) <= 1:
        return data
    mid = len(data) // 2
    left = merge_sort(data[:mid])
    right = merge_sort(data[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

print(merge_sort([6, 2, 7, 1]))
# Output: [1, 2, 6, 7]

Ready to test yourself?

Practise 2.1.3 questions

← Previous noteBubble sort2.1.3 Searching and sorting algorithms Next note →Insertion sort2.1.3 Searching and sorting algorithms

Back to Searching and sorting algorithms

Revise another OCR GCSE topic: Designing, creating and refining algorithms

def merge_sort(data): if len(data) <= 1: return data mid = len(data) // 2 left = merge_sort(data[:mid]) right = merge_sort(data[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 print(merge_sort([6, 2, 7, 1])) # Output: [1, 2, 6, 7]