Merge sort

How it works

1. Divide: split the list in half, again and again, until every sub-list has one item (a list of one item is already sorted).

2. Conquer and combine: merge pairs of sorted sub-lists into larger sorted lists until one sorted list remains.

Merging two sorted lists: compare the first items of each; move the smaller to the output; repeat; when one list runs out, copy the rest of the other.

Trace

Sort [38, 27, 43, 3, 9, 82, 10, 15].

Recursive code

def merge_sort(items):
    if len(items) <= 1:
        return items                    # base case
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

Efficiency

There are about log2 n levels of splitting, and each level of merging handles all n items, so the time complexity is O(n log n) in the best, average and worst case.

Benefits: consistently fast, even on large or reverse-ordered lists; stable (equal items keep their order). Drawbacks: needs extra memory O(n) for the merged lists; slower than simpler sorts on very small lists; no faster on data that is already sorted.

Worked example

Merge the sorted lists [3, 27, 38, 43] and [9, 10, 15, 82].

1. 3 vs 9: take 3. 27 vs 9: take 9. 27 vs 10: take 10. 27 vs 15: take 15.
2. 27 vs 82: take 27. 38 vs 82: take 38. 43 vs 82: take 43.
3. Left list is empty: copy 82.

Answer: [3, 9, 10, 15, 27, 38, 43, 82] using 7 comparisons

Check yourself

1. Merge sort is applied to [64, 25, 12, 22, 11, 90, 47, 5]. Give the four sub-lists after the first level of merging, as numbers separated by commas in order.
   Show answer

   25, 64, 12, 22, 11, 90, 5, 47. Pairs are merged: [[25, 64], [12, 22], [11, 90], [5, 47]].

2. For the same list, give the two sub-lists after the second level of merging, as numbers separated by commas in order.
   Show answer

   12, 22, 25, 64, 5, 11, 47, 90. [[12, 22, 25, 64], [5, 11, 47, 90]].

3. How many comparisons are made when merging [2, 5, 9] with [3, 4, 10]?
   Show answer

   5. 2v3 take 2; 5v3 take 3; 5v4 take 4; 5v10 take 5; 9v10 take 9; then copy 10: 5 comparisons.

4. How many levels of merging are needed to sort 32 items with merge sort?
   Show answer

   5. log2 32 = 5.

5. What is the worst-case time complexity of merge sort?
   • O(n log n)
   • O(n²)
   • O(n)
   • O(log n)
   Show answer

   O(n log n). Every case is O(n log n).

6. Which is a drawback of merge sort?
   • Its worst case is O(n²)
   • It only works on numbers
   • It needs extra memory to hold the merged lists
   • It cannot be written recursively
   Show answer

   It needs extra memory to hold the merged lists. Typical implementations need O(n) extra space.

7. What is the base case of a recursive merge sort?
   • A list with zero or one items, which is returned unchanged
   • A list of two items, which is swapped
   • When the list is half sorted
   • When the pivot is found
   Show answer

   A list with zero or one items, which is returned unchanged. A single item is already sorted.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.