Merge Sort

How merge sort works

Merge sort breaks a hard problem into easy ones, then stitches the answers back together. The hard problem is "sort this array." The easy problem is "merge two already-sorted arrays into one sorted array" — which can be done in linear time with two pointers.

The algorithm does this recursively:

1. Divide. Split the array in half. If it has one element or fewer, it's already sorted — return it.
2. Conquer. Recursively sort each half.
3. Merge. Walk through both sorted halves simultaneously with two pointers, picking the smaller front element each step and writing it to the output.

The recursion bottoms out at single-element arrays (which are trivially sorted), then unwinds back up. At each level, every element gets touched exactly once during a merge, so each level is O(n). With log₂(n) levels, the total cost is O(n log n).

When to use merge sort

• You need predictable performance. Quicksort is faster on average, but its worst case is O(n²). Merge sort guarantees O(n log n) on every input — there are no pathological cases.
• You need a stable sort. Merge sort preserves the relative order of equal elements, which matters when you're sorting records by multiple keys.
• You're sorting a linked list. No random access? No problem — merge sort doesn't need it. The split is just a pointer manipulation.
• The data doesn't fit in memory. Merge sort is the foundation of external sorting algorithms used by databases and Hadoop-era big data systems.

The trade-off is the O(n) auxiliary memory. If you're tight on RAM, a heap sort or in-place quicksort variant might be better.

Merge sort vs quicksort

	Merge sort	Quicksort
Time (average)	O(n log n)	O(n log n)
Time (worst)	O(n log n)	O(n²)
Space	O(n)	O(log n)
Stable	Yes	Not by default
In-place	No	Yes
Cache behavior	Poor (writes scattered)	Excellent (in-place)

In practice, quicksort is usually 2-3× faster than merge sort on random data because of cache-friendliness — but merge sort wins on guarantees. Many language standard libraries (Python, Java for objects, Rust) use hybrid algorithms like Timsort or pdqsort that combine the best of both.

Pseudo-code

function mergeSort(arr):
    if arr.length <= 1:
        return arr
    mid = floor(arr.length / 2)
    left  = mergeSort(arr[0:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

function merge(left, right):
    result = []
    i = 0; j = 0
    while i < left.length and j < right.length:
        if left[i] <= right[j]:
            result.push(left[i]); i++
        else:
            result.push(right[j]); j++
    while i < left.length: result.push(left[i++])
    while j < right.length: result.push(right[j++])
    return result

Note left[i] <= right[j] — using <= rather than < is what makes the sort stable. Equal elements from the left half always emplace first.

JavaScript implementation

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left  = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const out = new Array(left.length + right.length);
  let i = 0, j = 0, k = 0;
  while (i < left.length && j < right.length) {
    out[k++] = left[i] <= right[j] ? left[i++] : right[j++];
  }
  while (i < left.length)  out[k++] = left[i++];
  while (j < right.length) out[k++] = right[j++];
  return out;
}

Python implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

Python's built-in sorted() and list.sort() use Timsort — a merge sort variant that detects already-sorted runs and exploits them. On real-world data with structure (which is most data), Timsort approaches O(n) instead of O(n log n).

Optimizations worth knowing

• Switch to insertion sort for small subarrays (typically n < 16). Insertion sort has lower constant factors and dominates merge sort for tiny inputs. Standard libraries do this.
• Top-down vs bottom-up. The version above is top-down (recursive). Bottom-up merge sort is iterative — start by merging pairs of single elements, then pairs of 2-element runs, then pairs of 4-element runs. Same complexity, no recursion overhead.
• Reuse a single auxiliary buffer. Allocating a new temp array per merge is wasteful. Better implementations alternate between two buffers, halving allocation cost.
• Detect already-sorted halves. If left[last] <= right[0], no merge is needed — just concatenate. Timsort takes this much further.