Merge Sort

Intuition

Merge sort treats sorting as a divide-and-conquer problem. A large unsorted row is hard to reason about, but two small sorted rows are easy to combine: look only at the front value of each row, take the smaller one, and repeat. The algorithm keeps splitting until every range has one item, then rebuilds the array by merging sorted ranges back together.

How It Works

The recursive sort(lo, hi) call owns one contiguous range of the array. If the range has zero or one item, it is already sorted. Otherwise, merge sort splits it at the middle, sorts the left half, sorts the right half, and then merges the two sorted halves into a temporary array.

During merge, three pointers carry the whole invariant. i points at the next unused item in the left sorted run, j points at the next unused item in the right sorted run, and k points at the next slot in the temporary array (aux in code). While both runs still have candidates, the smaller front value is written to aux[k]. If the values are equal, this lesson uses <=, so the left item is chosen first. That one detail is what makes the sort stable.

After one side runs out, the other side is already sorted, so the remaining values can drain directly into the temporary array. Finally, the filled aux[lo..hi] range is copied back into arr[lo..hi].

Step By Step

The default input is [38, 12, 56, 7, 12, 41, 23]. The two 12 values are distinct: call them 12#1 from index 1 and 12#4 from index 4.

1. Split [0..6] into [0..3] and [4..6].
2. Split [0..3] into [0..1] and [2..3].
3. Split [0..1] into [0..0] and [1..1]; both are base cases.
4. Merge [38] and [12#1]. Compare 38 and 12#1, take 12#1, then drain 38, giving [12#1, 38].
5. Merge [56] and [7] into [7, 56], then merge [12#1, 38] with [7, 56] to produce [7, 12#1, 38, 56].
6. Split and merge the right half [12#4, 41, 23]. [41] and [23] merge into [23, 41], then [12#4] merges with that to become [12#4, 23, 41].
7. Final merge: compare 12#1 and 12#4. Because the code uses <=, the left 12#1 enters the buffer first. Then 12#4, 23, 38, 41, and 56 follow.

In the animation, watch the auxiliary row. The main row shows the current sorted runs; the lower row shows the merged result being built one slot at a time. The i, j, and k pointers are the important moving parts.

Complexity

The time stays O(n log n) because each level of recursion touches all n items during merging, and there are about log n split levels. The temporary array costs O(n) extra space.

Edge Cases

• Empty arrays and single-element arrays are already sorted.
• Duplicates are allowed; stable merge sort preserves their original relative order.
• Already sorted input still splits and merges, so it is not adaptive like insertion sort.
• Reverse sorted input follows the same number of split levels and merge passes.
• Odd-length ranges split unevenly; the left half gets floor((lo + hi) / 2).

Common Mistakes

• Using < instead of <= in the merge comparison. The output values are sorted either way, but stability is lost.
• Forgetting to drain the remaining left or right run after the main comparison loop.
• Copying the whole auxiliary array back instead of only lo..hi.
• Recomputing new arrays at every merge when the implementation is meant to use one reusable aux buffer.
• Returning after sorting the two halves but before calling merge, which leaves every small range sorted but the whole array unsorted.