# Merge Sort
## Algorithms — The Codex Coding
**URL:** https://thecodex.expert/coding/algorithms/sorting/merge-sort/
**Type:** algorithm | **Confidence:** high | **Last verified:** 2026-06-01

## CANONICAL DEFINITION
Merge sort is a comparison-based sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the two sorted halves into a single sorted array — achieving Theta(n log n) time in all cases with O(n) auxiliary space.

## COMPLEXITY
- best: Theta(n log n)
- average: Theta(n log n)
- worst: Theta(n log n)
- space: O(n)
- stability: stable

## REQUIRES
algorithms/sorting, concepts/recursion

## ENABLES
algorithms/searching

## COMMONLY CONFUSED WITH
O(n) space from merge buffer not call stack; merge sort != always fastest (quicksort faster in practice); recursion depth is O(log n) not O(n)

## SOURCES
- CLRS 4th ed. §2.3
- Knuth TAOCP Vol.3 §5.2.4
- Peters 2002 Timsort (CPython)
- Frigo et al. 1999 FOCS cache-oblivious

*The Codex Coding — thecodex.expert/coding/ — Free forever — Mumbai, India*