Merge Sort Algorithm Explained with Examples

By · · Algorithms

Merge sort is probably the first "serious" sorting algorithm most of us learn. It's elegant, predictable, and guaranteed O(n log n) no matter what input you throw at it. That consistency is why it shows up everywhere, from sorting linked lists to handling massive datasets that don't fit in memory.

The idea is dead simple: keep splitting the array in half until you can't anymore, then merge the small pieces back together in sorted order. That's it. The magic is in the merging step.

Interactive Visualization

Use the controls below to step through the algorithm or let it play automatically.

name: merge-sort
input: [38, 27, 43, 3, 9, 82, 10]
speed: 500

How Merge Sort Actually Works

Think of it like organizing a messy deck of cards. You split the deck in half, then split each half again, and keep going until you're holding individual cards. Now you start combining them back, but each time you merge two piles, you put them in order. By the time you've merged everything back into one pile, the whole deck is sorted.

Here's the high-level flow:

  1. Split the array into two halves
  2. Recursively sort each half
  3. Merge the two sorted halves into one sorted array

So the "divide" phase does almost no work. It just finds the midpoint and splits. The real work happens during the "conquer" phase when we merge sorted subarrays together.

Visualizing the Divide and Merge Phases

The top half of the diagram is the divide phase, splitting everything down to single elements. The bottom half is where merging happens, building sorted subarrays from the ground up.

Step-by-Step Walkthrough

Let's trace through sorting [38, 27, 43, 3, 9, 82, 10] so you can see every step.

Divide Phase

Level 0: [38, 27, 43, 3, 9, 82, 10]
            /                    \
Level 1: [38, 27, 43, 3]     [9, 82, 10]
           /        \            /      \
Level 2: [38, 27]  [43, 3]   [9, 82]  [10]
          /    \    /    \     /    \
Level 3: [38] [27] [43] [3] [9]  [82]

We keep splitting until every subarray has one element. A single element is already sorted by definition, so that's our base case.

Merge Phase

Now we work our way back up, merging pairs in sorted order.

Merging [38] and [27]:

Merging [43] and [3]:

Merging [9] and [82]:

Merging [27, 38] and [3, 43]:

Merging [9, 82] and [10]:

Final merge of [3, 27, 38, 43] and [9, 10, 82]:

Done. Every merge step produces a sorted subarray, and the final merge gives us the fully sorted result.

The Merge Process Visualized

The merge function walks through both arrays with two pointers. You always pick the smaller element from the front of either array. When one array runs out, dump whatever's left from the other.

Python Implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)


def merge(left, right):
    result = []
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # One of these will be empty, the other has remaining elements
    result.extend(left[i:])
    result.extend(right[j:])

    return result


# Try it out
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(f"Original: {arr}")
print(f"Sorted:   {sorted_arr}")
# Original: [38, 27, 43, 3, 9, 82, 10]
# Sorted:   [3, 9, 10, 27, 38, 43, 82]

Notice the <= in the comparison. That's what makes merge sort stable, meaning equal elements keep their original relative order. If you change it to <, you lose stability.

In-Place Variant (Saves Memory)

The version above creates new lists at every level. Here's one that sorts in place, which is more memory-friendly for large arrays.

def merge_sort_inplace(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    if left < right:
        mid = (left + right) // 2
        merge_sort_inplace(arr, left, mid)
        merge_sort_inplace(arr, mid + 1, right)
        merge_inplace(arr, left, mid, right)


def merge_inplace(arr, left, mid, right):
    left_copy = arr[left:mid + 1]
    right_copy = arr[mid + 1:right + 1]

    i = 0
    j = 0
    k = left

    while i < len(left_copy) and j < len(right_copy):
        if left_copy[i] <= right_copy[j]:
            arr[k] = left_copy[i]
            i += 1
        else:
            arr[k] = right_copy[j]
            j += 1
        k += 1

    while i < len(left_copy):
        arr[k] = left_copy[i]
        i += 1
        k += 1

    while j < len(right_copy):
        arr[k] = right_copy[j]
        j += 1
        k += 1


arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort_inplace(arr)
print(arr)  # [3, 9, 10, 27, 38, 43, 82]

This still uses O(n) extra space for the temporary copies during merging. True in-place merge sort exists but it's significantly more complex and rarely worth the tradeoff in practice.

Time and Space Complexity

Case Time Complexity Space Complexity
Best O(n log n) O(n)
Average O(n log n) O(n)
Worst O(n log n) O(n)

Here's why it's always O(n log n): we split the array log(n) times (halving each time), and at each level we do O(n) work to merge everything. That multiplication gives us n log n regardless of the input.

The space complexity is O(n) because we need temporary arrays during merging. You also have O(log n) stack frames from recursion, but the O(n) merge space dominates.

When Should You Use Merge Sort?

Merge sort isn't always the best choice. Quicksort is faster in practice for most in-memory sorting. But there are specific situations where merge sort wins.

Sorting linked lists. This is merge sort's sweet spot. You can split a linked list by walking with slow/fast pointers, and merging two sorted linked lists takes O(1) extra space. Quicksort is awkward on linked lists because random access is expensive.

External sorting. When your data doesn't fit in memory, you need to sort chunks on disk and merge them. Merge sort's sequential access pattern is perfect for this. Databases use variations of merge sort for exactly this reason.

When you need a stable sort. Merge sort preserves the relative order of equal elements. If you're sorting records by one field but want to keep a previous ordering for ties, merge sort handles that naturally. Quicksort doesn't guarantee stability.

Guaranteed worst-case performance. Quicksort degrades to O(n^2) on bad inputs (though randomized pivot selection mostly fixes this). If you absolutely can't afford worst-case blowup, merge sort gives you a firm O(n log n) guarantee every time.

Common Interview Problems Using Merge Sort

Merge sort is one of those algorithms that pays dividends once you really understand the merge step. That pattern of combining two sorted sequences shows up in tons of places beyond just sorting.