# Top Down Merge Sort

# 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.

```text id="3qz9t1"
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.

```text id="9t2kxp"
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

```python id="2n4d5k"
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
```

```go id="9a8f2m"
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]
	}
}
```