Merge Sort

Category: Classical
Difficulty: Intermediate
Time Complexity: O(n log n)
Space Complexity: O(n)

Overview

Merge Sort divides the array into halves recursively until each sub-array has one element, then merges them back in sorted order. It guarantees O(n log n) time in all cases but requires O(n) extra space for the merge buffer.

Try It

Web: Open in Eigenvue →

Python:

import eigenvue
eigenvue.show("merge-sort")

Default Inputs

{
  "array": [
    38,
    27,
    43,
    3,
    9,
    82,
    10
  ]
}

Input Examples

Default unsorted

{
  "array": [
    38,
    27,
    43,
    3,
    9,
    82,
    10
  ]
}

Power of two (8 elements)

{
  "array": [
    8,
    3,
    6,
    1,
    5,
    2,
    7,
    4
  ]
}

Already sorted

{
  "array": [
    1,
    2,
    3,
    4,
    5,
    6
  ]
}

Single element

{
  "array": [
    42
  ]
}

Code

Pseudocode

function mergeSort(array):
  if length(array) <= 1:
    return array
  for size = 1, 2, 4, ... while size < n:
    for left = 0, 2*size, 4*size, ...:
      mid = min(left + size - 1, n - 1)
      right = min(left + 2*size - 1, n - 1)
      merge(array, left, mid, right)

function merge(array, left, mid, right):
  aux = copy of array[left..right]
  i = left, j = mid + 1, k = left
  while i <= mid and j <= right:
    if aux[i] <= aux[j]: array[k] = aux[i]; i++
    else: array[k] = aux[j]; j++
    k++
  copy remaining elements

Python

def merge_sort(arr):
    n = len(arr)
    size = 1
    while size < n:
        for left in range(0, n, 2 * size):
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)
            merge(arr, left, mid, right)
        size *= 2

def merge(arr, left, mid, right):
    temp = arr[left:right + 1]
    i, j, k = 0, mid - left + 1, left
    while i <= mid - left and j < len(temp):
        if temp[i] <= temp[j]:
            arr[k] = temp[i]; i += 1
        else:
            arr[k] = temp[j]; j += 1
        k += 1
    while i <= mid - left:
        arr[k] = temp[i]; i += 1; k += 1
    while j < len(temp):
        arr[k] = temp[j]; j += 1; k += 1

Key Concepts

Divide and Conquer

Merge Sort divides the problem into smaller sub-problems (halving), solves them, and combines (merges) the results.

Stability

When equal elements appear, we always take from the left half first, preserving their original relative order.

Guaranteed O(n log n)

Unlike QuickSort, Merge Sort always runs in O(n log n) regardless of input order. The trade-off is O(n) extra space.

Auxiliary Space

The merge step requires a temporary buffer of size n. This is the main disadvantage compared to in-place sorting algorithms.

Common Pitfalls

Forgetting to copy back: After merging into the auxiliary buffer, the values must be copied back into the main array. Forgetting this means subsequent merges operate on stale data.
Off-by-one in merge boundaries: The mid index belongs to the LEFT sub-array [left..mid], and the right starts at mid+1. Getting this wrong duplicates or skips elements.

Quiz

Q1: What is the space complexity of Merge Sort?

A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)

Show answer

Answer: C) O(n)

Merge Sort needs O(n) auxiliary space for the merge buffer, plus O(log n) for the recursion stack. The dominant term is O(n).

Q2: Is Merge Sort stable?

A) Yes
B) No