SortingAlgorithmaka mergesort

Merge Sort

Split the array in half, sort each half recursively, then merge the two sorted halves in linear time.

▶ VisualizePattern: Two PointersPractice (3)
Progress

Overview

Merge sort is the canonical Divide and Conquer sort: split into halves, sort each recursively, and merge the two sorted halves with a linear two-pointer sweep. It runs in O(n log n) in every case, is stable, and its access pattern is sequential, which makes it the basis for external sorting on disk and for sorting linked lists.

Its cost is O(n) auxiliary space for the merge buffer (in-place variants exist but are slow or complex). It is not adaptive in the textbook version, though checking a[mid] <= a[mid+1] before merging skips already-ordered halves. TimSort — Python's sorted, Java's Arrays.sort for objects — is an adaptive, run-detecting merge sort.

comparisonO(n log n)stabledivide and conquerexternal sortlinked list

Intuition

A mental model before the formal terms.

Two sorted stacks of exam papers can be combined into one sorted stack by repeatedly taking whichever top paper has the smaller number — one glance per paper. To sort an unsorted stack, split it into halves until each stack has one paper (trivially sorted), then combine stacks upward. Every paper participates in log₂ n merges.

How it works

  1. If the range has fewer than two elements, return (base case).
  2. Compute mid and recursively sort [lo, mid] and [mid + 1, hi].
  3. Merge: with pointers i, j at the start of each half, copy the smaller element (taking from the left on ties for stability) into a buffer; append whatever remains.
  4. Copy the buffer back into [lo, hi].
  5. Bottom-up variant: merge runs of size 1, 2, 4, … iteratively, avoiding recursion.

Why it works

Merging two sorted sequences is correct by induction: the smaller of the two heads is the smallest remaining element overall, since each sequence is sorted.

Recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) by the Master theorem: log₂ n levels, each doing O(n) merge work.

Stability: when a[i] == b[j], the left element is copied first, preserving original relative order across all merge levels.

Recognition

How to tell a problem wants this.

  • A stable O(n log n) sort is required (sorting records by one field while preserving another order).
  • Sorting a linked list — merge sort needs no random access and runs in O(1) extra space on lists.
  • Counting inversions, "count of smaller numbers after self", reverse pairs — problems solved by instrumenting the merge step.
  • Data does not fit in memory (external sort) or guaranteed worst-case time is needed.
  • Merging k sorted lists.
“sorted array” → Two Pointers“merge k sorted” → Divide and Conquer“reverse a linked list” → Linked List Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/54Start with 8 elements. Merge sort splits the array in halves until pieces of size one, then merges sorted pieces back together.
Left halfRight halfHeads being comparedMerged / sorted
PseudocodeLearn Merge Sort →
1mergeSort(a, lo, hi):
2  if lo >= hi: return
3  mid = (lo + hi) // 2
4  mergeSort(a, lo, mid)
5  mergeSort(a, mid+1, hi)
6  merge(a, lo, mid, hi):
7    i = lo, j = mid+1, buf = []
8    while i <= mid and j <= hi:
9      if a[i] <= a[j]: buf.push(a[i++]) else buf.push(a[j++])
10    append leftovers of both halves to buf
11    copy buf back into a[lo..hi]
Complexity
best O(n log n)
avg O(n log n)
worst O(n log n)
space O(n)
Speed

Pseudocode

1mergeSort(a, lo, hi):
2  if lo >= hi: return
3  mid = lo + (hi - lo) // 2
4  mergeSort(a, lo, mid); mergeSort(a, mid + 1, hi)
5  i = lo, j = mid + 1, buf = []
6  while i <= mid and j <= hi:
7    if a[i] <= a[j]: buf.push(a[i++]) else: buf.push(a[j++])
8  append remaining a[i..mid] and a[j..hi] to buf
9  copy buf into a[lo..hi]

Implementations

1def merge_sort(a: list[int]) -> None:
25 · Entry point allocates the buffer once
3    buf = [0] * len(a)
4 
51 · Recursive sort over [lo, hi] with a shared buffer
6    def sort(lo: int, hi: int) -> None:
7        if lo >= hi:
8            return
92 · Split and recurse on both halves
10        mid = lo + (hi - lo) // 2
11        sort(lo, mid)
12        sort(mid + 1, hi)
13        if a[mid] <= a[mid + 1]:  # halves already ordered: skip merge
14            return
153 · Merge the two sorted halves into buf
16        i, j, k = lo, mid + 1, lo
17        while i <= mid and j <= hi:
18            if a[i] <= a[j]:  # ties -> left: stable
19                buf[k] = a[i]
20                i += 1
21            else:
22                buf[k] = a[j]
23                j += 1
24            k += 1
25        while i <= mid:
26            buf[k] = a[i]
27            i += 1
28            k += 1
29        while j <= hi:
30            buf[k] = a[j]
31            j += 1
32            k += 1
334 · Copy the merged range back
34        a[lo:hi + 1] = buf[lo:hi + 1]
35 
36    sort(0, len(a) - 1)
Walkthrough
  1. The nested sort closure captures a and buf; Python closures can read outer lists and mutate them in place without nonlocal.
  2. (hi - lo) // 2 is floor division; Python ints never overflow so (lo + hi) // 2 would also be safe.
  3. The skip-merge check makes sorted input cheap.
  4. The merge writes into buf by index; <= keeps ties on the left (stable).
  5. Copy-back uses slice assignment a[lo:hi + 1] = buf[lo:hi + 1], which creates a temporary O(hi - lo) list — an extra copy per merge that C++ avoids.
Complexity (this implementation)
time O(n log n) in all cases · space O(n) buffer + O(log n) stack

Slice assignment allocates a temporary per merge (O(n) per level, O(n log n) total copies, still O(n) live memory). The common merge_sort(a[:mid]) style allocates fresh lists per level too.

Language notes
  • sorted() / list.sort() are TimSort — a stable, adaptive merge sort in C — so hand-written merge sort is only for learning or for instrumented merges (inversion counting).
  • heapq.merge(*iterables) merges already-sorted iterables lazily, useful for external sorts.
  • Recursion depth is log2(n), far below the default limit of 1000.
Common mistakes in this language
  • Using left.pop(0) in the merge — O(n) per pop.
  • Using < instead of <=, which breaks stability.
  • Mixing the return-a-new-list style with in-place mutation.
  • Rebinding buf = ... inside the closure without nonlocal (creates a local, breaks the algorithm).
Language differences that matter here
  • Buffer cost: the C++ version allocates one std::vector and merges in contiguous memory; Python slice assignment copies the merged range again per merge, and the popular a[:mid] slicing style allocates O(n) per recursion level in Python and JS (slice).
  • Stability: the hand-written merge is stable in all four languages thanks to <=. Library equivalents: std::stable_sort (C++), Array.prototype.sort (stable since ES2019), Python sorted (TimSort, always stable); std::sort is NOT stable.
  • Midpoint overflow: (lo + hi) / 2 can overflow int in C++; JS numbers are doubles (safe to 2^53); Python ints are unbounded.
  • JS [10, 2, 5].sort() compares as strings; this merge sort compares numerically like C++ and Python.
  • Linked lists: C++ std::list::sort and a hand-written Python/JS list merge use O(1) extra space; the array version needs O(n).

Complexity

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)

O(1) extra space on linked lists. Stable, not in-place, not adaptive (unless run detection is added). O(log n) recursion depth.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Guaranteed O(n log n) with stability — sorting objects by key, multi-key sorts done in passes.
  • Linked lists (no random access; O(1) extra space).
  • External sorting of data larger than memory; the merge step streams sequentially.
  • Divide-and-conquer counting problems: inversions, count-smaller-after-self, reverse pairs.
  • Parallel sorting — halves are independent.
Avoid it when

Alternatives

Quick SortHeap SortTimSortRadix Sort
Compare: Merge Sort vs Quick Sort

Common mistakes

  • Using < instead of <= when comparing heads — takes from the right on ties and destroys stability.
  • Allocating a new buffer at every recursion level (O(n log n) allocations); allocate once and reuse.
  • Off-by-one on mid: the halves must be [lo, mid] and [mid + 1, hi], and mid must be lo + (hi - lo) / 2 so both halves shrink.
  • Forgetting to copy the leftover tail of one half after the other is exhausted.

Interview patterns

  • Count inversions: during merge, when taking a[j] from the right, add mid - i + 1 to the count.
  • Sort a linked list in O(n log n): split with fast/slow pointers, merge by relinking.
  • Merge k sorted lists by pairwise merging in a tournament (or a heap).
  • Count of smaller numbers after self / reverse pairs (LeetCode 315, 493).
Interview questions on this
Mock interviews

Example problems

Reverse Linked ListeasyMerge k Sorted ListshardMerge Intervalsmedium
Don't delegate understanding
The manifesto →