Merge Sort in Python

Merge sort is one of the most elegant sorting algorithms ever invented. Designed by John von Neumann in 1945, it was one of the first algorithms to embrace the now-famous divide and conquer strategy. 🚀

The idea is beautifully simple: a list of one item is already sorted, so if we keep cutting our problem in half until we hit single-item lists, we just need a clever way to merge sorted pieces back together. That merging trick is the secret sauce, making merge sort an unshakeable O(n log n) sort — fast, predictable, and a stable sort that preserves the original order of equal elements. It's the backbone of Python's Timsort, powers external sort for files bigger than RAM, and fits naturally in distributed systems.

How It Works

Merge sort follows three crisp phases:

1. Divide — Split the array roughly in half.

2. Conquer — Recursively sort each half.

3. Combine — Merge the two sorted halves into one.

Let's walk through [38, 27, 43, 3, 9, 82, 10]. First, we recursively split until every piece is size 1:

            [38, 27, 43, 3, 9, 82, 10]
           /                          \
      [38, 27, 43]              [3, 9, 82, 10]
      /         \               /            \
   [38]      [27, 43]        [3, 9]        [82, 10]
              /    \          /   \          /    \
           [27]   [43]      [3]   [9]     [82]   [10]

Now we merge back up, keeping each level sorted:

   [38]  [27, 43]      [3, 9]    [82, 10]
      \   /              \          /
   [27, 38, 43]        [3, 9, 10, 82]
          \               /
        [3, 9, 10, 27, 38, 43, 82]

Notice we never compared 38 to 82 directly. Merge sort only does the comparisons it absolutely needs.

The Merge Step

The merge function is where the magic happens. Given two already-sorted arrays, we walk both with two pointers i and j, always picking the smaller of the two front elements, appending it, and advancing that pointer. When one side runs out, we dump the rest of the other side onto the end — it's already sorted!

Why is this O(n)? Every comparison results in exactly one element being appended to the output. With n total elements, we do at most n comparisons and n appends. No element is ever visited twice. That linear merge step is the engine that makes merge sort tick. ✨

One subtle detail: the comparison left[i] <= right[j] (using <=, not <) is what makes merge sort stable. When two elements are equal, the one from the left half goes first, preserving original ordering.

Recursive Top-Down vs Iterative Bottom-Up

The example code is the top-down recursive version: start with the whole array, recurse downward, merge on the way back up. Intuitive and reads beautifully.

There's also a bottom-up iterative version: treat each element as a sorted run of size 1, merge adjacent pairs into runs of size 2, then 4, then 8, until one sorted run remains. No recursion, often friendlier to caches. Timsort uses this flavour with adaptive run sizes. Same complexity either way.

Complexity Analysis

All three time cases are identical — that consistency is merge sort's superpower. Quick sort can degrade to O(n^2) on adversarial input; merge sort cannot.

Why O(n log n)?

Here's the intuition. Each level of recursion splits the problem in half, so the recursion tree is log_2 n levels deep. At every level, the total merging work across all sub-arrays adds up to n (every element gets touched once per level). Multiply: n work per level times log n levels = O(n log n).

Formally, the recurrence is T(n) = 2T(n/2) + O(n). The master theorem says the work is evenly balanced between recursion and combine, giving us exactly Theta(n log n). No magic — just clean math.

Common Pitfalls

Real-World Uses

Merge Sort vs Quick Sort

Reach for merge sort when you need a worst-case guarantee, are sorting linked lists, or stability matters. Reach for quick sort when you need raw speed on in-memory arrays and can tolerate occasional bad cases.

Frequently Asked Questions

Is merge sort stable?

Yes! As long as the merge uses <= (not <), equal items keep their original relative order — one of merge sort's killer features.

Is merge sort in-place?

No. The standard implementation needs O(n) extra memory. In-place merge sort variants exist but are complicated and slow in practice.

Why is merge sort better than quick sort for linked lists?

Quick sort needs random access to swap around a pivot, which linked lists don't provide cheaply. Merge sort walks sequentially and merges by re-linking pointers — no extra memory beyond the original nodes!

Does Python use merge sort?

Kind of! Python's sorted() uses Timsort, a hybrid of merge sort and insertion sort that exploits naturally occurring sorted runs.

Can merge sort be parallelised?

Absolutely — the two recursive calls are completely independent, so left and right halves can sort on different cores.

What's the space complexity really?

O(n) for auxiliary arrays plus O(log n) for the recursion stack. Most analyses just say O(n) since that dominates.