# Merge Sort

> Sort by recursively splitting in half, sorting each side, and merging back — guaranteed O(n log n) regardless of input, stable.

- **Category**: Algorithms
- **Subcategory**: sorting
- **Canonical URL**: https://designpattern.fyi/algorithms/merge-sort/

---

## Description
**Intent**: Sort with guaranteed O(n log n) performance on any input — no pivot trap, no worst case — while preserving the relative order of equal elements.

**Context**: You need predictable performance on adversarial or unknown input, or you need a stable sort (equal elements must preserve their original relative order). Quick sort's O(n²) worst case on sorted or nearly-sorted input is unacceptable. Merge sort has no such trap.

**Solution**: Recursively split the array in half until each sub-array is a single element (trivially sorted). Merge adjacent sorted sub-arrays by repeatedly picking the smaller front element from either side — until the full sorted array is reconstructed. Every level of the recursion does O(n) merge work across O(log n) levels.



## Use Cases
When worst-case performance matters and O(n²) is unacceptable. When stability is required — equal elements must maintain original relative order. External sorting of data too large for RAM. Sorting linked lists, where merge sort's merge step needs no random access.



## Implementation Example

```javascript
function mergeSort(arr) {
  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(left, right) {
  const result = [];
  let i = 0, j = 0;

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

  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Usage
const unsorted = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(unsorted)); // [11, 12, 22, 25, 34, 64, 90]
```



## Trade-offs


### Advantages

- Guaranteed O(n log n) — no input shape triggers a worse case

- Stable — equal elements preserve their original relative order

- Excellent for linked lists and external (disk-based) sorting




### Considerations & Drawbacks

- O(n) extra space — requires an auxiliary array the size of the input

- Slower than quick sort in practice on arrays — extra allocation and copy overhead adds up

- More implementation complexity than quick sort