Merge Sort

Merge sort is a divide-and-conquer sorting algorithm that splits the array in half, recursively sorts each half, and merges the two sorted halves by repeatedly taking the smaller front value. It guarantees O(n log n) time complexity in every case, uses O(n) auxiliary space, and is stable.

The insight is that merging is easy even though sorting is hard. Hand someone two stacks of exam papers, each already in alphabetical order, and they can combine them without thinking: look at the top page of each stack, take whichever comes first, repeat. Merge sort manufactures that easy situation everywhere — split until every stack has one page (trivially sorted), then let the easy merge do all the real work on the way back up.

How Merge Sort Works

The recursive sort(lo, hi) owns one contiguous range. A range of zero or one item is already sorted — that is the base case. Otherwise it splits at mid = (lo + hi) // 2, sorts the left half, sorts the right half, and merges them.

The merge runs on three pointers. i points at the front of the left sorted run, j at the front of the right run, k at the next free slot in the auxiliary array. While both runs have pages left, the smaller front value is copied to aux[k]. On a tie, the comparison is arr[i] <= arr[j], so the left value goes first — that one character is the entire stability guarantee. When one run empties, the other drains straight into aux, and finally aux[lo..hi] is copied back into arr[lo..hi].

Merge Sort Step by Step

The default input is [38, 12, 56, 7, 12, 41, 23]. It contains two 12s on purpose — call them 12a (index 1) and 12b (index 4) — because they are about to demonstrate stability.

The recursion descends the left half first. [0..6] splits at mid 3 into [0..3] and [4..6]; [0..3] splits into [0..1] and [2..3]; [0..1] splits into the singletons [38] and [12a]. First merge: 38 > 12a, take the right value, then drain 38 — [12a, 38]. Same shape for [2..3]: 56 > 7 gives [7, 56]. Merging those two runs interleaves them into [7, 12a, 38, 56], and the whole left half is sorted.

The right half [12b, 41, 23] splits at mid 5. [12b] and [41] merge without drama into [12b, 41], which then merges with [23]: take 12b, then 23 beats 41, then drain 41 — [12b, 23, 41].

The final merge combines [7, 12a, 38, 56] with [12b, 23, 41]. Take 7. Now the fronts are 12a and 12b — a dead tie, and <= takes the left one: 12a enters the buffer before 12b, preserving their original order. Then 38 > 12b takes 12b, 38 > 23 takes 23, 38 ≤ 41 takes 38, 56 > 41 takes 41, and 56 drains. Copy back: [7, 12a, 12b, 23, 38, 41, 56].

In the animation, the divide map at the top shows which range is active while the workbench below plays the current merge: the i and j pointers sit on the two run fronts, and each chosen value drops into the aux row one slot at a time before the result commits back. The tie beat in the final merge is labeled explicitly — watch which 12 moves first.

Time and Space Complexity

Every level of the recursion touches all n elements during merging, and halving produces about log n levels — n log n, with no bad inputs and no lucky ones. The price is the O(n) auxiliary buffer. The animated version is the standard top-down recursive form with a single reusable aux array.

This is the trade against quick sort in one sentence: merge sort buys a worst-case guarantee and stability, and pays in memory.

Edge Cases

• Empty or one-element array — base case, returned untouched.
• Already sorted input — same splits, same merges, same O(n log n). Merge sort is not adaptive; it cannot notice it got lucky.
• Reverse-sorted input — identical cost. Every merge just happens to take from the right run first.
• Duplicates — preserved in original relative order; the default input's two 12s show it directly.
• Odd-length ranges — the split is uneven; the left half gets the extra element via (lo + hi) // 2.

Common Mistakes

• Using < instead of <= in the merge comparison. The output is still sorted, but ties now favor the right run and stability silently dies — the bug no test on plain integers will ever catch.
• Forgetting the drain loops. After one run empties, the other's remaining values must still be copied; dropping them loses elements.
• Copying back the whole aux instead of lo..hi. Slots outside the current range hold stale values from earlier merges.
• Allocating a fresh buffer in every merge. Correct but wasteful; the standard form reuses one n-sized aux for the whole sort.
• Returning after the two recursive calls but before merge. Every half ends up sorted and the array as a whole does not.