Merge Sort Algorithm Explained

Merge sort recursively splits a list in half until each piece has one element, then merges the pieces back together in sorted order.

Published November 15, 2026

Merge sort splits the list in half, sorts each half recursively, then merges the two sorted halves into one. It guarantees O(n log n) time and is stable, at the cost of O(n) extra memory.

The concept

Divide until pieces have one element (trivially sorted), then merge pairs: repeatedly take the smaller front item of the two halves.

Its predictable performance makes it ideal for linked lists and external sorting of data too large for memory.

Divide and merge

[6, 2, 8, 4]
[6, 2] [8, 4]
[2, 6] [4, 8] ← sorted halves
[2, 4, 6, 8] ← merged

Practical examples

JavaScript

function mergeSort(a) {
  if (a.length < 2) return a
  const m = a.length >> 1
  const l = mergeSort(a.slice(0, m)), r = mergeSort(a.slice(m))
  const out = []
  while (l.length && r.length) out.push(l[0] <= r[0] ? l.shift() : r.shift())
  return [...out, ...l, ...r]
}

Python

def merge_sort(a):
    if len(a) < 2: return a
    m = len(a)//2
    l, r = merge_sort(a[:m]), merge_sort(a[m:])
    out = []
    while l and r: out.append(l.pop(0) if l[0] <= r[0] else r.pop(0))
    return out + l + r

Complexity

time O(n log n) always · space O(n) · stable

Common mistakes

  • Using shift() (O(n)) in the merge for big arrays.
  • Using <, not <=, and breaking stability.
  • Ignoring the extra memory.

Key takeaways

  • Divide, sort, merge.
  • Always O(n log n), stable.
  • Needs O(n) extra space.

FAQ

Why is it good for linked lists?

Merging needs no random access or extra array.

Is it faster than quicksort?

Often slightly slower in memory-bound arrays but more predictable.

More General articles