Merge Sort Visualization — Step by Step

Step 1: Divide until sorting is trivial

Merge Sort starts from a cheeky observation: an array of one element is already sorted. So it splits the array in half, splits each half in half, and keeps going until only single elements remain. Take [6, 2, 8, 4]: it splits into [6, 2] and [8, 4], then into [6], [2], [8], [4]. No comparisons have happened yet — the divide phase is pure bookkeeping. All the real work is deferred to the way back up, where pairs of already-sorted pieces get combined. Halving repeatedly gives the recursion log₂ n levels, a number that matters shortly.

Step 2: The merge — two fingers, one output

Merging two sorted lists is the heart of the algorithm. Put a finger on the front of each list; repeatedly compare the two fingered values, copy the smaller one out, and advance that finger. Merging [2, 6] and [4, 8]: compare 2 vs 4 → take 2; compare 6 vs 4 → take 4; compare 6 vs 8 → take 6; the left list is empty, so 8 is copied across without a comparison. Result: [2, 4, 6, 8]. Each element is touched once, so merging two halves of total length k costs O(k) — never more.

Watching the full example

Back to [6, 2, 8, 4]. The singles merge pairwise: [6] + [2] → [2, 6], and [8] + [4] → [4, 8]. Then the final merge combines [2, 6] and [4, 8] into [2, 4, 6, 8], as traced above. Notice the shape of the work: every level of the recursion merges *all n elements exactly once* — the singles level, the pairs level, the final level. In the visualizer you can see this as waves: highlights sweep the whole array once per level, and there are log₂ n waves.

Why it is always O(n log n)

That shape is the entire complexity proof. There are about log₂ n levels of merging, each level does O(n) copying-and-comparing, so the total is O(n log n) — best case, worst case, every case. This is Merge Sort’s defining trait: it is completely indifferent to the input. Sorted, reversed, random, adversarial — the split points depend only on array *length*, never on values, so performance never degrades. Compare that with Quick Sort, whose partition sizes depend on the data and can collapse to O(n²). You can race them to see the average-case story.

The price: O(n) extra space

The merge step cannot easily happen in place: writing the merged output over the top of the two input halves would destroy values before they are read. So each merge copies the halves into temporary arrays first — this implementation slices them out — costing O(n) auxiliary memory. That is the classic trade against Quick Sort, which partitions in place. The copy is less painful than it sounds: sequential reads and writes are cache-friendly, and for linked lists the merge needs no extra space at all, which is why Merge Sort is the standard choice for sorting a linked list.

Stability comes free

Look at the comparison in the merge: left[i] <= right[j]. When the two fingered values are equal, the tie goes to the left half — and every element in the left half came before every element in the right half in the original array. Equal elements therefore never cross each other, making Merge Sort naturally stable. This single <= (rather than <) is load-bearing: it is why Timsort, the merge-based hybrid inside Python and Java, can sort records by one field without scrambling a previous ordering on another field.

JavaScript

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

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    // <= keeps equal elements in order (stability)
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}

Python

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

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= keeps the sort stable
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Java

public static void mergeSort(int[] arr, int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = (lo + hi) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid, hi);
    merge(arr, lo, mid, hi);
}

private static void merge(int[] arr, int lo, int mid, int hi) {
    int[] left = java.util.Arrays.copyOfRange(arr, lo, mid);
    int[] right = java.util.Arrays.copyOfRange(arr, mid, hi);
    int i = 0, j = 0, k = lo;
    while (i < left.length && j < right.length) {
        // <= keeps equal elements in order (stability)
        arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    }
    while (i < left.length) arr[k++] = left[i++];
    while (j < right.length) arr[k++] = right[j++];
}