Implementing a recursive merge sort

The idea

• Base case: a list with 0 or 1 items is already sorted.
• Divide: split the list at the middle index, mid = len(items) // 2.
• Conquer: merge sort each half recursively.
• Combine: merge the two sorted halves by repeatedly taking the smaller front item.

Splitting a list of n items in half repeatedly gives about log2 n levels, and each level does about n comparisons when merging.

The code

def merge_sort(items):
    if len(items) <= 1:                 # base case: already sorted
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[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]:         # <= keeps equal items in order (stable)
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    result.extend(left[i:])             # one of these is empty
    result.extend(right[j:])
    return result

# merge_sort and merge as above

data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))
print(data)
print(merge_sort(["pear", "fig", "apple"]))

Output:

[3, 9, 10, 27, 38, 43, 82]
[38, 27, 43, 3, 9, 82, 10]
['apple', 'fig', 'pear']

This version returns a new sorted list and leaves the original unchanged.

Watching the splits

Adding a print line to the start of merge_sort, indented by depth, shows the recursion splitting the list until single items remain:

Output:

[38, 27, 43, 3, 9, 82, 10]
  [38, 27, 43]
    [38]
    [27, 43]
      [27]
      [43]
  [3, 9, 82, 10]
    [3, 9]
      [3]
      [9]
    [82, 10]
      [82]
      [10]

Properties

Worked example

Show the merge of [3, 27, 38, 43] and [9, 10, 82].

1. Compare 3 and 9: take 3. Compare 27 and 9: take 9. 27 and 10: take 10. 27 and 82: take 27. 38 and 82: take 38. 43 and 82: take 43.
2. The left list is used up, so extend with the rest of the right list: 82.
3. Result: [3, 9, 10, 27, 38, 43, 82]

Answer: Six comparisons, then the leftover 82 is copied across without comparing.

Check yourself

1. merge is the function from the lesson. What does this print? ```python def merge_sort(items): if len(items) <= 1: # base case: already sorted return items mid = len(items) // 2 left = merge_sort(items[:mid]) right = merge_sort(items[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]: # <= keeps equal items in order (stable) result.append(left[i]) i = i + 1 else: result.append(right[j]) j = j + 1 result.extend(left[i:]) # one of these is empty result.extend(right[j:]) return result print(merge([2, 5, 9], [1, 5, 6, 12])) ```
   Show answer

   [1, 2, 5, 5, 6, 9, 12]. Take the smaller front item each time (left first on a tie), then copy the leftover 12. Output: `[1, 2, 5, 5, 6, 9, 12]`

2. This version of merge counts comparisons. What does it print? ```python def merge_sort(items): if len(items) <= 1: # base case: already sorted return items mid = len(items) // 2 left = merge_sort(items[:mid]) right = merge_sort(items[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 global comparisons while i < len(left) and j < len(right): comparisons = comparisons + 1 if left[i] <= right[j]: # <= keeps equal items in order (stable) result.append(left[i]) i = i + 1 else: result.append(right[j]) j = j + 1 result.extend(left[i:]) # one of these is empty result.extend(right[j:]) return result comparisons = 0 merge([1, 3, 5], [2, 4, 6]) print(comparisons) ```
   Show answer

   5. 1 v 2, 3 v 2, 3 v 4, 5 v 4, 5 v 6: then the left list is empty and 6 is copied. That is `5` comparisons.

3. A list of 32 items is merge sorted. How many levels of splitting are there before every sublist has one item?
   Show answer

   5. 32 to 16 to 8 to 4 to 2 to 1: log2 32 = 5 levels.

4. This uses the same split as merge_sort. What does it print? ```python def merge_sort(items): if len(items) <= 1: # base case: already sorted return items mid = len(items) // 2 left = merge_sort(items[:mid]) right = merge_sort(items[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]: # <= keeps equal items in order (stable) result.append(left[i]) i = i + 1 else: result.append(right[j]) j = j + 1 result.extend(left[i:]) # one of these is empty result.extend(right[j:]) return result def first_split(items): mid = len(items) // 2 return items[:mid], items[mid:] print(first_split([7, 2, 9, 4, 1])) ```
   Show answer

   ([7, 2], [9, 4, 1]). mid = 5 // 2 = 2, so the left half has 2 items and the right half 3. Output: `([7, 2], [9, 4, 1])`

5. This is the lesson's merge sort, changed so that it compares only the score (item 1 of each pair). What does this print? ```python def merge_sort(items): if len(items) <= 1: # base case: already sorted return items mid = len(items) // 2 left = merge_sort(items[:mid]) right = merge_sort(items[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i][1] <= right[j][1]: # <= keeps equal items in order (stable) result.append(left[i]) i = i + 1 else: result.append(right[j]) j = j + 1 result.extend(left[i:]) # one of these is empty result.extend(right[j:]) return result pairs = [("Ana", 2), ("Ben", 1), ("Cy", 2), ("Di", 1)] print([name for name, score in merge_sort(pairs)]) ```
   Show answer

   ['Ben', 'Di', 'Ana', 'Cy']. The merge compares only the scores. On a tie it takes from the left half first, so players with equal scores stay in their original order: Ben before Di, Ana before Cy. Output: `['Ben', 'Di', 'Ana', 'Cy']`

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

   O(n log n). It always splits in half (log n levels) and merges n items per level.

7. Why must merge_sort have the base case `if len(items) <= 1: return items`?
   • Without it, the recursion would never stop splitting
   • It sorts lists of two items
   • It merges the two halves
   • It removes duplicates
   Show answer

   Without it, the recursion would never stop splitting. A list of 0 or 1 items cannot be split further and is already sorted; without the base case the calls would recurse until a RecursionError.

8. What is a disadvantage of merge sort compared with an in-place sort?
   • It is slower on large lists
   • It needs extra memory proportional to the list size to hold the merged lists
   • It only works on numbers
   • It cannot be written recursively
   Show answer

   It needs extra memory proportional to the list size to hold the merged lists. The merge step builds new lists, using O(n) extra memory.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification, Issue 1 (March 2026)
• Pearson Edexcel IAL Computer Science Unit 4 Programming Language Subset (PLS)
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 and Unit 4)

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