Merge Sort Step by Step — Visual Guide with Animation

Merge Sort is built on one observation that sounds almost too obvious to be useful: merging two already-sorted lists into one sorted list is easy. You just look at the front of each list, take whichever element is smaller, and repeat. Merge Sort turns that trivial operation into a full sorting algorithm by manufacturing the sorted lists itself — it splits the array down to single elements (which are trivially sorted), then merges its way back up.

The payoff is the most predictable mainstream sorting algorithm there is: O(n log n) time on *every* input — sorted, reversed, random, adversarial, it does not care. In this guide we will trace the divide phase on a concrete 8-element array, walk the merge operation pointer by pointer, and see exactly where that guarantee comes from.

Phase 1: divide until nothing is left to divide

Take the array [6, 3, 8, 1, 5, 9, 2, 4]. The divide phase repeatedly splits every segment at its midpoint. No comparing, no moving — just recursive bookkeeping that bottoms out at single elements:

[6, 3, 8, 1, 5, 9, 2, 4]        level 0 — the full array
[6, 3, 8, 1]    [5, 9, 2, 4]    level 1 — two halves
[6, 3] [8, 1]   [5, 9] [2, 4]   level 2 — four quarters
[6][3] [8][1]   [5][9] [2][4]   level 3 — eight singletons

An 8-element array needs exactly 3 levels of splitting because 2³ = 8 — in general, log₂ n levels. Hold onto that number; it is one half of the complexity argument. Now the recursion unwinds and every split is undone by a merge: [6] and [3] merge into [3, 6], [8] and [1] into [1, 8], then [3, 6] and [1, 8] into [1, 3, 6, 8], and so on until the mirror image of the tree above has been rebuilt — sorted.

Phase 2: the merge, traced pointer by pointer

All the real work happens in merge. It takes two sorted runs and combines them using two read pointers — i into the left run, j into the right — and one write position in an output buffer. At each step, compare left[i] with right[j], copy the smaller one out, and advance that pointer only. Here is the final, biggest merge of our example: left = [1, 3, 6, 8], right = [2, 4, 5, 9].

1. Compare 1 and 2 → take 1 from the left → output [1]
2. Compare 3 and 2 → take 2 from the right → output [1, 2]
3. Compare 3 and 4 → take 3 from the left → output [1, 2, 3]
4. Compare 6 and 4 → take 4 from the right → output [1, 2, 3, 4]
5. Compare 6 and 5 → take 5 from the right → output [1, 2, 3, 4, 5]
6. Compare 6 and 9 → take 6 from the left → output [1, 2, 3, 4, 5, 6]
7. Compare 8 and 9 → take 8 from the left → output [1, 2, 3, 4, 5, 6, 8]
8. Left run exhausted → copy the rest of the right run → [1, 2, 3, 4, 5, 6, 8, 9]

Two things to notice. First, the merge never backs up — each pointer only moves forward, so merging n total elements costs at most n−1 comparisons and exactly n copies. Second, once one run is exhausted (step 8), the remainder of the other run is copied over without any comparisons at all: it is already sorted and everything in it is known to be larger.

mergeSort(array, low, high):
  if low >= high:
    return                        // 0 or 1 elements — sorted
  mid = (low + high) / 2
  mergeSort(array, low, mid)      // sort left half
  mergeSort(array, mid + 1, high) // sort right half
  merge(array, low, mid, high)    // combine the sorted halves

merge(array, low, mid, high):
  copy array[low..high] into temp
  i = start of left run, j = start of right run
  for k from low to high:
    if left run is exhausted:        take from right
    else if right run is exhausted:  take from left
    else if temp[i] <= temp[j]:      take temp[i]   // <= keeps it stable
    else:                            take temp[j]

Why it is O(n log n) — in every case

The complexity argument fits in two sentences once you picture the recursion tree. Each level does O(n) total work: at any level, every element of the array belongs to exactly one merge happening at that level, and merging touches each element a constant number of times — so level by level, the merges sum to n operations no matter how the array is chopped up. And there are log₂ n levels, because the segments halve at every step and you can only halve n about log₂ n times before hitting 1.

Multiply the two: log n levels × O(n) work per level = O(n log n). Crucially, nothing in that argument depends on the values in the array. The split is always exactly in half — unlike Quicksort, where a badly chosen pivot can make the "halves" absurdly lopsided and drag the running time to O(n²). Merge Sort has no bad inputs, no pathological orderings, no luck involved. For a 1,000,000-element array that is roughly 20 levels of a million operations each, versus the ~500 billion operations a quadratic sort like Bubble Sort would need.

Stability — the quiet superpower

Merge Sort is stable: elements that compare equal keep their original relative order. Look back at the merge pseudocode — on a tie (temp[i] <= temp[j]) it takes from the *left* run, and the left run contains the elements that came first in the original array. That single <= is the entire mechanism.

Why care? Because real data is records, not bare numbers. Suppose you sort a list of employees by name, then sort the result by department. With a stable sort, employees within each department are still alphabetical — the second sort preserved the first one's work, and you have effectively sorted by (department, name) without writing a compound comparator. With an unstable sort like naive Quicksort or Selection Sort, the name order inside each department is scrambled. This is exactly why the sort methods in Python and Java are *required* to be stable, and why they are built on merging.

The cost: O(n) extra space

The merge cannot easily happen in place — writing the merged output over the top of the runs you are still reading from would destroy them. So practical implementations copy into an auxiliary buffer of size n. That has real consequences: allocation overhead, extra memory traffic, and roughly double the footprint of an in-place sort. (In-place merge variants exist but pay for it with much worse constants, so almost nobody uses them.) This is the main trade against Quicksort, which needs only the recursion stack.

Where Merge Sort lives in the real world

• Timsort — the standard sort in Python and for objects in Java — is a merge sort at heart: it finds naturally sorted runs already present in the data and merges them, falling back to binary insertion sort for tiny runs. Stability and the n log n guarantee come straight from the merge machinery.
• External sorting. When data does not fit in RAM, you sort chunk-sized pieces in memory, write each sorted run to disk, then merge the runs with sequential reads. Merging only ever needs the *front* of each run, which is exactly what slow, sequential storage is good at serving. Database engines sort this way for large ORDER BY and index builds.
• Linked lists. Merge Sort is the natural list sort: splitting and merging are pointer operations, needing no random access and no auxiliary array at all.
• Parallel sorting. The two halves are completely independent until the final merge, so they can be sorted on different cores with no coordination.

Common misconceptions

• "The divide step does the sorting." No — dividing compares nothing. All ordering decisions happen in the merges on the way back up. Quicksort is the opposite: it works on the way down and its "combine" step is free.
• "Merging two sorted arrays needs a full re-sort." It needs one linear pass. That is the entire point — merging is O(n), not O(n log n).
• "O(n log n) means Merge Sort is always the fastest choice." Same Big-O class as Quicksort, but the buffer copying and poorer cache behaviour usually make it a constant factor slower on in-memory arrays. You pick Merge Sort for stability, guarantees, lists, or disk — not raw speed.

Try it yourself

The recursion tree is abstract until you see it move: halves splitting apart, singletons pairing up, sorted runs zipping together level by level. Run Merge Sort on a random array and watch the merge pointers leapfrog each other, then feed it a sorted array and confirm it does exactly the same amount of work — the guarantee, live.