---
title: Merge Sort
description: A stable divide-and-conquer sorting algorithm that guarantees O(n log n).
tokens: ~343
---

# Merge Sort

Merge sort divides the array in half, recursively sorts each half, and then merges the sorted halves back together.

## How It Works

1. **Divide** the array into two halves.
2. **Recursively sort** each half.
3. **Merge** the two sorted halves into one sorted array.

## Example

```typescript
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(a: number[], b: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;

  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }

  return [...result, ...a.slice(i), ...b.slice(j)];
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]
```

## Complexity

| Case | Time | Space |
|---|---|---|
| All cases | O(n log n) | O(n) |

### Why Always O(n log n)?

Unlike quicksort, merge sort always divides exactly in half, so the recursion depth is always log n, and each level does O(n) work for merging.

## Key Properties

- **Stable** — equal elements keep their original order.
- **Not in-place** — requires O(n) extra memory for the merge step.
- **Predictable** — no worst-case degradation like quicksort.