Knowledge organisersSearching and sorting algorithms

Standard sorting algorithms: Merge sort

Knowledge organiser

Searching and sorting algorithms

2.1.3d

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.

Key points

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.
Key Point:The MERGING process itself produces the sorted order — there is NO separate sorting step after merging.
Common Misconception:Merging unsorted groups and then sorting them afterwards is WRONG. Each merge step produces a correctly ordered list.
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'.

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]

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]