2.2.2(d), 2.3.1(f)Algorithms and EfficiencyCore

Merge Sort and Divide and Conquer

Merge sort divides a sequence into smaller parts and then combines sorted results. The merge step, rather than merely splitting the input, is what establishes the final order.

35 min Sorting Algorithms

What you'll be able to do

Trace recursive splitting and merging
Implement a correct two-way merge
Explain O(n log n) time and storage trade-offs

Divide until the base cases are sorted

A sequence of zero or one item is already sorted. Split a larger sequence into two parts, sort each recursively and merge their results. The split need not produce equal sizes when the length is odd, but each recursive part must become smaller.

Draw the split tree and then work back upwards. The order in which recursive calls execute is different from the order in which values appear in the final answer. Splitting into single items does not itself tell the program how to combine them.

Merge two sorted sequences

Maintain a position in each input. Compare the next unused values and append the smaller to the result, advancing only that input’s position. When one input is exhausted, append the other input’s remaining suffix. The sorted-input assumption justifies each choice.

A stable merge chooses the left item first on equality when the left sequence represents earlier original items. Forgetting to advance a pointer can create a loop; advancing both loses a value. Check that the merged output contains each original item exactly once, including duplicates.

Explain the growth of work

At a given recursion level, merging across all subproblems processes a total proportional to n items. A roughly halving split creates O(log n) levels, producing O(n log n) time for the usual array merge sort. This is more scalable than quadratic sorting for large n.

A common array implementation uses O(n) additional merge storage plus a logarithmic call stack; slicing and allocation can affect practical overhead. Implementations for linked structures or specialised in-place variants differ, so attach storage claims to the version being discussed.

Python 3

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
    return result + left[i:] + right[j:]

print(merge([2, 7], [1, 6]))

Scroll horizontally to see the full code or table.

A stable merge of two already sorted lists.

Work through the problem

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.

Example 1Trace merge sort on [7,2,6,1].

1Split into [7,2] and [6,1], then into single-item lists.

2Merge the pairs to [2,7] and [1,6], then compare across them to obtain [1,2,6,7].

Answer[1,2,6,7].

Example 2Why append the unused suffix after one input is exhausted?

1The remaining suffix is already sorted.

2No values remain in the other input that could need to precede it.

AnswerIt preserves all remaining values without unnecessary comparisons.

Common mistakes to avoid

Showing only splits without the merges.

Trace how ordered results are built upwards.

Dropping the remaining suffix.

Ensure every original element appears exactly once.

Key takeaways

Divide and conquer reduces the problem size.
Merging relies on sorted input prefixes.
Level-by-level work explains O(n log n).

Test yourself

Answer a few questions, then review anything you missed.

Next step

Keep practising

Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.

Browse practice topics

Related lessons

All 4 lessons

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 return result + left[i:] + right[j:] print(merge([2, 7], [1, 6]))