Top Down Merge Sort

Top down merge sort is the canonical recursive form of merge sort. It starts from the full array, splits it into halves recursively until single elements remain, then merges upward.

This form directly follows the divide and conquer recurrence and is the most common presentation in textbooks.

Problem

Given an array $A$ of length $n$ , reorder it such that:

A[0] \le A[1] \le \dots \le A[n-1]

Algorithm

Split first, then solve subproblems, then merge.

top_down_merge_sort(A, l, r):
    if l >= r:
        return

    mid = (l + r) // 2

    top_down_merge_sort(A, l, mid)
    top_down_merge_sort(A, mid + 1, r)

    merge(A, l, mid, r)

The merge step works on index ranges instead of slices.

merge(A, l, mid, r):
    i = l
    j = mid + 1
    temp = []

    while i <= mid and j <= r:
        if A[i] <= A[j]:
            append A[i] to temp
            i += 1
        else:
            append A[j] to temp
            j += 1

    append remaining A[i..mid]
    append remaining A[j..r]

    copy temp back into A[l..r]

Example

Let:

A = [7, 3, 6, 2]

Recursive split:

[7, 3, 6, 2]
[7, 3] and [6, 2]
[7], [3], [6], [2]

Merge upward:

[7] + [3] → [3, 7]
[6] + [2] → [2, 6]
[3, 7] + [2, 6] → [2, 3, 6, 7]

Correctness

Each recursive call sorts a smaller segment. The base case produces sorted segments of size one. The merge step preserves order by always selecting the smallest available element. By structural induction over recursion depth, the full array becomes sorted.

Complexity

Recurrence:

T(n) = 2T(n/2) + O(n)

T(n)=2T(n/2)+n

Solution:

T(n) = O(n \log n)

metric	value
time	$O(n \log n)$
space	$O(n)$
recursion depth	$O(\log n)$

Properties

property	value
stable	yes
in-place	no
cache efficiency	moderate
parallelizable	yes

Notes

Top down merge sort performs many recursive calls and may incur overhead on small arrays. Practical implementations often switch to insertion sort for small segments to reduce constant factors.

Implementation

def top_down_merge_sort(a):
    temp = [0] * len(a)

    def sort(l, r):
        if l >= r:
            return
        mid = (l + r) // 2
        sort(l, mid)
        sort(mid + 1, r)
        merge(l, mid, r)

    def merge(l, mid, r):
        i, j, k = l, mid + 1, l

        while i <= mid and j <= r:
            if a[i] <= a[j]:
                temp[k] = a[i]
                i += 1
            else:
                temp[k] = a[j]
                j += 1
            k += 1

        while i <= mid:
            temp[k] = a[i]
            i += 1
            k += 1

        while j <= r:
            temp[k] = a[j]
            j += 1
            k += 1

        for i in range(l, r + 1):
            a[i] = temp[i]

    sort(0, len(a) - 1)
    return a

func TopDownMergeSort(a []int) {
	n := len(a)
	temp := make([]int, n)

	var sort func(int, int)
	sort = func(l, r int) {
		if l >= r {
			return
		}
		mid := (l + r) / 2
		sort(l, mid)
		sort(mid+1, r)
		merge(a, temp, l, mid, r)
	}

	sort(0, n-1)
}

func merge(a, temp []int, l, mid, r int) {
	i, j, k := l, mid+1, l

	for i <= mid && j <= r {
		if a[i] <= a[j] {
			temp[k] = a[i]
			i++
		} else {
			temp[k] = a[j]
			j++
		}
		k++
	}

	for i <= mid {
		temp[k] = a[i]
		i++
		k++
	}

	for j <= r {
		temp[k] = a[j]
		j++
		k++
	}

	for i := l; i <= r; i++ {
		a[i] = temp[i]
	}
}