The Concept#

Merge Sort is a classic Divide and Conquer algorithm. It works by:

  1. Dividing the unsorted list into sublists, each containing one element.
  2. Repeatedly merging sublists to produce new sorted sublists until there is only one sublist remaining.

Code Implementation#

Below is the standard recursive implementation of Merge Sort:

Complexity Analysis#

  • Time Complexity: O(N log N) in all cases (best, worst, average). The tree of recursive splits is log N levels deep, and merging elements at each level takes O(N) operations.
  • Space Complexity: O(N) auxiliary space to allocate arrays during merging.

Interactive Lab: Merge Sort#

Let's take the example in the visualization below: [5, 2, 8, 1, 9, 3, 10, 4, 6, 7]. The left, mid and right chips mark the range each recursive call owns, so you can read the call stack straight off the bars.

Two things are worth waiting for:

  1. Nothing moves for a while. sort(0, 9) splits into sort(0, 4), which splits into sort(0, 2), which splits into sort(0, 1). The recursion drills all the way down the left edge before a single bar changes position. The first real work is a two-element merge of 5 and 2.
  2. Then the merges get bigger. [2, 5] merges with [8], that result merges with [1, 9], and so on. Each merge is a single left-to-right pass over an already-sorted pair of runs, never a re-sort. The last merge combines the two sorted halves [1, 2, 5, 8, 9] and [3, 4, 6, 7, 10] in one sweep.

That second point is the O(N log N): every level of the split tree touches all ten bars exactly once, and there are only about log₂ 10 ≈ 3.3 levels of splitting to do.

Key Advantages#

  • Stable Sort: Preserves the relative order of equal elements.
  • Guaranteed Performance: Does not suffer from worst-case O(N^2) behaviors like Quick Sort.