# Merge Sort

# Merge Sort

Merge sort is a divide and conquer sorting algorithm. It splits the input into smaller parts, sorts each part recursively, then merges the sorted parts into a single sorted sequence.

It guarantees stable ordering and predictable time complexity. It performs well on large datasets and external memory systems.

## Problem

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

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

## Algorithm

Divide the array into two halves. Sort each half. Merge the two sorted halves.

```text
merge_sort(A):
    if length(A) <= 1:
        return A

    mid = length(A) // 2
    left = merge_sort(A[0:mid])
    right = merge_sort(A[mid:n])

    return merge(left, right)
```

The merge step combines two sorted arrays into one sorted array.

```text
merge(left, right):
    i = 0
    j = 0
    result = []

    while i < length(left) and j < length(right):
        if left[i] <= right[j]:
            append left[i] to result
            i += 1
        else:
            append right[j] to result
            j += 1

    append remaining elements of left
    append remaining elements of right

    return result
```

## Example

Let:

$$
A = [5, 2, 4, 1]
$$

Split:

* left: [5, 2]
* right: [4, 1]

Sort recursively:

* [5, 2] → [2, 5]
* [4, 1] → [1, 4]

Merge:

| step | left | right | result       |
| ---- | ---- | ----- | ------------ |
| 1    | 2    | 1     | [1]          |
| 2    | 2    | 4     | [1, 2]       |
| 3    | 5    | 4     | [1, 2, 4]    |
| 4    | 5    | -     | [1, 2, 4, 5] |

Final result:

$$
[1, 2, 4, 5]
$$

## Correctness

The recursion ensures each subarray is sorted. The merge step preserves sorted order because it always selects the smallest available element from the two inputs. By induction on subarray size, the final output is sorted.

## Complexity

| metric         | value         |
| -------------- | ------------- |
| time (best)    | $O(n \log n)$ |
| time (worst)   | $O(n \log n)$ |
| time (average) | $O(n \log n)$ |

Recurrence:

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

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

Solution:

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

Space:

$$
O(n)
$$

for the auxiliary merge array.

## Properties

| property       | value |
| -------------- | ----- |
| stable         | yes   |
| in-place       | no    |
| adaptive       | no    |
| parallelizable | yes   |

## When to Use

Use merge sort when:

* stable sorting is required
* worst case guarantees matter
* data is large or stored externally
* parallel execution is available

Avoid it when memory is constrained, since it requires additional space proportional to input size.

## Implementation

```python
def merge_sort(a):
    if len(a) <= 1:
        return a

    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])

    return merge(left, right)

def merge(left, right):
    i = j = 0
    result = []

    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
```

```go
func MergeSort(a []int) []int {
	if len(a) <= 1 {
		return a
	}

	mid := len(a) / 2
	left := MergeSort(a[:mid])
	right := MergeSort(a[mid:])

	return merge(left, right)
}

func merge(left, right []int) []int {
	i, j := 0, 0
	result := make([]int, 0, len(left)+len(right))

	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}

	result = append(result, left[i:]...)
	result = append(result, right[j:]...)
	return result
}
```