Merge Sort

A divide-and-conquer algorithm that splits the array and merges the sorted halves.

Worth knowing first

Insertion Sort

#How does it work?

Merge sort uses "divide and conquer": it splits the array in half, sorts each half separately, then merges the two sorted halves.

Splitting continues recursively until the pieces have a single element. A one-element array is already sorted.

The real work happens in the merge step: the front elements of the two sorted halves are compared and the smaller one is taken. When one half runs out, the rest of the other is appended as is.

#Live animation

$ merge_sort --visualizespace · ← → · r · sStep 1/57

The array is split in half until pieces have one element, then the pieces are merged in order.

Speed

Comparisons: 0Moves: 0ComparingTaken from leftTaken from rightIn place

mergeSort(a, lo, hi):
  if lo >= hi: return
  mid = (lo + hi) / 2
  mergeSort(a, lo, mid); mergeSort(a, mid + 1, hi)
  merge: repeatedly take the smaller front element
  append whatever is left

#Step by step

01If the array has one element, it is already sorted; return.
02Split the array in the middle.
03Sort the left half with merge sort.
04Sort the right half with merge sort.
05Merge the two sorted halves: repeatedly take the smaller of the two front elements, then append what is left.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def merge_sort(a: list[int]) -> list[int]:
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])

    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        # "<=" takes from the left on ties, which keeps the sort stable.
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


print(*merge_sort([5, 1, 4, 2, 8, 3]))

#Complexity

Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)
Extra memory	O(n)
Stable?	Yes
In place?	No

The array is halved log₂ n times and every level merges n elements in total: n · log n. This doesn't depend on the order of the data, so O(n log n) is guaranteed even in the worst case. Merging usually needs an extra array of size n. (The animation merges in place by shifting elements so you can see each move.)

#When to use it?

Ideal when you need guaranteed O(n log n) time and stability. It is also the standard way to sort linked lists and data too large for memory (external sorting). Python's and Java's object sorting use Timsort, which is based on merge sort.

#Practice

Easy

1/3

Which approach does merge sort use?

1Divide and conquer
2Greedy
3Dynamic programming
4Backtracking

1–4 pick · ← → move · enter continue

Medium

1/1

When merging the sorted halves [2, 5, 8] and [1, 6, 9], which two elements are taken first?

11, then 2
22, then 1
31, then 6
42, then 5

1–4 pick · ← → move · enter continue

Hard

1/1

Which merge rule makes merge sort stable?

1On ties, take from the left half
2On ties, take from the right half
3Always take the larger one
4Pick halves at random

1–4 pick · ← → move · enter continue

#Up next

Lessons that build on this one: