The Divide-and-Conquer Approach

Divide-and-conquer solves a problem in three stages:

1. Divide — break it into smaller sub-problems of the same kind
2. Conquer — solve those (usually by recursing, until they are trivial)
3. Combine — assemble the sub-answers into the answer

The sub-problems are independent. That is what distinguishes it from dynamic programming, where they overlap.

Merge sort: the syllabus example

Already decomposed in Module 3. Here it is as the three stages:

• Divide — split the list in half
• Conquer — sort each half (same problem, half the size)
• Combine — merge two sorted lists into one

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

                    ... now merge back up ...

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

Splitting takes no thought; all the work is in the merge. Two sorted lists combine by repeatedly taking whichever front element is smaller.

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.extend(left[i:])
    result.extend(right[j:])
    return result


def merge_sort(items):
    if len(items) <= 1:
        return items[:]
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))

Why splitting helps

Sorting by comparing every pair takes roughly $n^2$ comparisons. Merge sort halves the problem repeatedly, so it needs about $n \log_2 n$.

At 10,000 items that is around 750 times less work. The syllabus does not require this analysis — the numbers are here only to show why halving matters.

Advantages

The syllabus asks for these directly.

1. Efficiency. Repeatedly halving turns quadratic work into something far smaller. This is the main reason the approach exists.

2. It suits parallel work. The sub-problems are independent, so two halves can genuinely be sorted at the same time on different processors — impossible when sub-problems depend on each other.

3. Simple, natural code. The solution mirrors the problem's structure, as Module 3's decomposition showed.

4. Cache-friendly. Sub-problems eventually become small enough to sit in fast memory, which matters on real hardware.

Disadvantages

1. Recursion overhead. Every call costs a stack frame. For small inputs the bookkeeping can exceed the saving — which is why real libraries switch to a simple insertion sort below about 10–20 elements.

2. Extra memory. Merge sort builds new lists while merging, needing roughly as much additional space as the original. An in-place sort such as insertion sort needs almost none.

3. Risk of stack overflow. Deep recursion on very large inputs can exhaust the stack, as in Module 3.

4. It does not fit every problem. If sub-problems overlap, dividing alone causes the recomputation that ruins naive Fibonacci. That problem needs dynamic programming, not divide-and-conquer.

Other divide-and-conquer algorithms

• Binary search — halve the search range each step
• Quick sort — partition around a pivot, sort each side
• Tower of Hanoi — move n−1 discs, move one, move n−1 back

The distinction to hold onto

Both decompose. Only one needs a memory.