Skip to content

Divide and Conquer

First PublishedByAtif Alam

Difficulty: Medium. ROI: Low.

Other common names: D&C, recursive divide; merge sort, quicksort; insertion sort (baseline).

When to use: Use when the problem can be split into independent subproblems of the same type, and the solution can be combined from subproblem results (e.g. mergesort, quicksort, Strassen, some recurrences). This page covers merge sort and quicksort as examples; insertion sort is mentioned as a non–divide-and-conquer baseline.

Idea: Divide the input into smaller instances, solve them recursively (or as base cases), then combine the results. Often gives O(n log n) or similar when the combine step is linear.

Time / space: Depends on recurrence (e.g. T(n) = 2T(n/2) + O(n) → O(n log n)). Space O(log n) for recursion stack if splitting evenly.

Example #1 — Merge Sort

Section titled “Example #1 — Merge Sort”

Split the array in half, recursively sort each half, then merge the two sorted halves by repeatedly taking the smaller front element. Base case: length ≤ 1 is already sorted.

Sample input and output

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # [3, 9, 10, 27, 38, 43, 82]
  • Sample input: arr = [38, 27, 43, 3, 9, 82, 10].
  • Sample output: [3, 9, 10, 27, 38, 43, 82].

Code (with inline comments)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # sort first half
    right = merge_sort(arr[mid:])  # sort second half
    return merge(left, right)


def merge(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1   # take from a, advance i
        else:
            out.append(b[j]); j += 1   # take from b, advance j
    out.extend(a[i:])
    out.extend(b[j:])
    return out

Line-by-line:

  • if len(arr) <= 1: return arr — Base case: a single element (or empty) is already sorted.
  • mid = len(arr) // 2 — Split the array in half. arr[:mid] is the first half, arr[mid:] is the second.
  • left = merge_sort(arr[:mid]) — Recursively sort the first half. Same for right. We assume the recursive calls return sorted arrays.
  • return merge(left, right) — Merge two sorted arrays into one sorted array by repeatedly taking the smaller of the two front elements.
  • merge(a, b): i, j — Two indices pointing at the next unused element in a and b. We compare a[i] and b[j], append the smaller to out, and advance that index. When one list is exhausted, we append the rest of the other with extend.

Execution trace (numbered list)

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

  1. Step 1: Split into [38,27,43,3] and [9,82,10]. Recursively sort each.
  2. Step 2: Left half splits to [38,27], [43,3]; sort → [27,38], [3,43]; merge → [3,27,38,43].
  3. Step 3: Right half splits to [9,82], [10]; sort → [9,82], [10]; merge → [9,10,82].
  4. Step 4: Merge [3,27,38,43] and [9,10,82] → [3,9,10,27,38,43,82].

Execution trace (code with step comments)

# merge_sort([38,27,43,3,9,82,10])
#   left = merge_sort([38,27,43,3]) → [3,27,38,43]
#   right = merge_sort([9,82,10]) → [9,10,82]
#   return merge([3,27,38,43], [9,10,82]) → [3,9,10,27,38,43,82]

Execution trace (ASCII diagram)

Divide until single elements, then merge upward.

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

Example #2 — Quicksort

Section titled “Example #2 — Quicksort”

Pick a pivot (e.g. the last element), partition the array so all elements smaller than the pivot are on the left and larger on the right, then recursively sort the left and right parts. Average time O(n log n); worst case O(n²) when the pivot is always min or max.

Sample input and output

arr = [38, 27, 43, 3, 9, 82, 10]
quicksort(arr, 0, len(arr) - 1)
print(arr)  # [3, 9, 10, 27, 38, 43, 82]
  • Sample input: arr = [38, 27, 43, 3, 9, 82, 10].
  • Sample output: [3, 9, 10, 27, 38, 43, 82] (in-place).

Code (with inline comments)

def quicksort(arr, lo, hi):
    if lo >= hi:
        return
    pivot_idx = partition(arr, lo, hi)  # partition; pivot ends at pivot_idx
    quicksort(arr, lo, pivot_idx - 1)   # sort left of pivot
    quicksort(arr, pivot_idx + 1, hi)   # sort right of pivot


def partition(arr, lo, hi):
    pivot = arr[hi]   # last element as pivot
    i = lo            # place for smaller elements
    for j in range(lo, hi):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]   # put pivot in place
    return i

Line-by-line:

  • if lo >= hi: return — Base case: zero or one element in the range is already sorted.
  • partition(arr, lo, hi) — Rearrange arr[lo..hi] so elements ≤ pivot are left, pivot at final index; returns that index.
  • pivot = arr[hi] — Use the last element as pivot (other choices are possible).
  • i = lo — Index where we place the next element that is ≤ pivot. j scans from lo to hi-1; when arr[j] ≤ pivot, we swap arr[j] with arr[i] and advance i.
  • arr[i], arr[hi] = arr[hi], arr[i] — Put the pivot at index i so everything left is ≤ pivot and everything right is > pivot.

Execution trace (numbered list)

For [38, 27, 43, 3, 9, 82, 10] with pivot 10:

  1. Partition: Move elements ≤ 10 to the left: 3 and 9 swap into place; pivot 10 goes to index 2. Result: [3, 9, 10, 38, 43, 82, 27] (conceptually: left [3,9], pivot 10, right [38,43,82,27]).
  2. Recurse left on [3, 9]: trivial (sorted).
  3. Recurse right on [38, 43, 82, 27]: pivot 27; partition → [27, 38, 43, 82]; recurse on [38, 43, 82] → pivot 82 → [38, 43, 82] sorted.
  4. Combined: [3, 9, 10, 27, 38, 43, 82].

Execution trace (code with step comments)

# quicksort([38,27,43,3,9,82,10], 0, 6)
#   partition: pivot=10 → arr = [3, 9, 10, 38, 43, 82, 27], pivot_idx=2
#   quicksort(arr, 0, 1) → [3, 9] sorted
#   quicksort(arr, 3, 6) → [27, 38, 43, 82] sorted
#   final: [3, 9, 10, 27, 38, 43, 82]

Execution trace (ASCII diagram)

First partition around 10, then recurse on left and right.

      [38,27,43,3,9,82,10]   pivot=10
              |
    partition → [3,9 | 10 | 38,43,82,27]
                    |
        +-----------+-----------+
        |                       |
   [3,9] pivot=9           [38,43,82,27] pivot=27
     [3,9] sorted          partition → [27 | 38,43,82]
                                  |
                          [38,43,82] pivot=82
                            [38,43,82] sorted

Other sort: insertion sort

Section titled “Other sort: insertion sort”

Insertion sort is a simple O(n²) baseline that does not use divide and conquer. It keeps a sorted prefix and repeatedly inserts the next element into the correct position in that prefix by shifting larger elements right. It’s useful for small n or nearly sorted data, and as a comparison point for merge sort and quicksort.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Each iteration expands the sorted prefix by one element; the inner loop shifts elements to make room for key.