Merge Sort Complete Guide

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Related Sorting Guides

Bubble, merge, and quick sort are tightly related. Compare them side-by-side to understand tradeoffs in runtime, memory, and stability.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

How It Compares

Real-World Stories and Company Examples

Recursive merge sort

function mergeSort(values: number[]): number[] {
  if (values.length <= 1) return values
  const midIndex = Math.floor(values.length / 2)
  const leftHalf = mergeSort(values.slice(0, midIndex))
  const rightHalf = mergeSort(values.slice(midIndex))

  const merged: number[] = []
  let leftIndex = 0
  let rightIndex = 0
  while (leftIndex < leftHalf.length && rightIndex < rightHalf.length) {
    if (leftHalf[leftIndex] <= rightHalf[rightIndex]) merged.push(leftHalf[leftIndex++])
    else merged.push(rightHalf[rightIndex++])
  }

  return [...merged, ...leftHalf.slice(leftIndex), ...rightHalf.slice(rightIndex)]
}

Common Problems and Failure Modes

• Forgetting the memory overhead of temporary merge arrays.
• Incorrect merge pointer updates causing dropped/duplicated values.
• Not preserving stability when equal values occur.
• Recursive stack depth concerns in constrained environments.
• Using merge sort when in-place constraints are strict.

Tips and Tricks

• Merge sort is your stable O(n log n) baseline when predictability matters.
• Keep merge logic isolated in helper function to prevent pointer bugs.
• Use merge sort for linked lists where random access is costly.
• For very large data, external merge-sort strategy scales better than in-memory quick hacks.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

Real-system usage signals

• Stable ordering is guaranteed, which matters in multi-key sorts.
• Predictable worst-case performance for production pipelines.
• Works well for linked lists and external/distributed sort workflows.

LeetCode-specific tips (including pattern-identification signals)

• Identification signal: stable O(n log n) behavior is needed and extra memory is acceptable.
• Identification signal: divide-then-merge phrasing appears, especially with linked lists or external sorting.
• If predictable worst-case performance matters more than in-place memory use, merge sort is a strong fit.
• For Merge Sort questions, start by naming the core invariant before writing code.
• Use the constraint section to set time/space target first, then pick the data structure/algorithm.
• Solve one tiny example by hand and map each transition to your variables before implementing.
• Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
• During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.