Merge Sort
A stable O(n log n) divide-and-conquer sorting algorithm that recursively splits an array and merges sorted halves.
Merge sort is a comparison-based sorting algorithm invented by John von Neumann in 1945. It follows the divide-and-conquer pattern: split the array in half, recursively sort each half, then merge the two sorted halves into one sorted array. Because the merge step only compares the fronts of the two halves, it runs in linear time, and the recursion depth is logarithmic — so merge sort guarantees O(n log n) comparisons in every case, including the worst case, unlike naive quicksort implementations.
The merge step is where the work happens. It walks two sorted subarrays with two pointers, repeatedly copying the smaller of the two front elements into an output array, then copies any remaining elements. The algorithm is stable: equal elements keep their original relative order, which matters when sorting records by multiple keys. Its main cost is memory: it needs O(n) auxiliary space for the output array, so in-place sorting algorithms such as heapsort are preferred where memory is tight.
function merge_sort(a, left, right):
if right - left <= 1: return
mid = (left + right) / 2
merge_sort(a, left, mid)
merge_sort(a, mid, right)
merge(left, mid, right) // merge two sorted runs
Because it reads and writes data sequentially rather than randomly, merge sort is the natural choice for sorting data that does not fit in memory: external sorting of large files uses repeated merge passes, and most databases sort with merge-based strategies. Its guaranteed O(n log n) behavior is the benchmark against which other comparison sorts are measured in Big O analysis, alongside the O(n log n) search cost of binary search on sorted data.
Tags
algorithms divide and conquer recursion sorting