Skip to content

Volume ITechnology

4.0.27 — Merge Sort ​

Classic · Medium · LeetCode 912 (Sort an Array), LeetCode 148 (Sort List) · the most-asked "real" sort

The problem ​

Sort a list in increasing order without sort(), and do it in O(n \log n) time, even in the worst case.

[38, 27, 43, 3, 9, 82, 10]  →  [3, 9, 10, 27, 38, 43, 82]

Why the first three sorts cannot do this ​

Bubble, selection and insertion sort all move elements one step at a time, or search the whole remaining list each round. 4.0.24 showed that any sort which only swaps neighbours needs about n^2/4 swaps on a random list. To go faster, a sort must do something smarter. Merge sort's smart move is divide and conquer: split the problem into smaller copies of itself, solve those, and combine the answers.

John von Neumann wrote merge sort in 1945, for one of the very first stored-program computers. It is one of the oldest algorithms written for a computer.

The idea ​

Two facts make it work.

  1. A list of one element is already sorted. There is nothing to compare.
  2. Two sorted lists can be merged into one sorted list in linear time. That is exactly what 4.0.19 did, by repeatedly taking the smaller of the two fronts.

So: split the list in half. Sort the left half (by the same method). Sort the right half (by the same method). Merge the two sorted halves. The halves keep splitting until they are single elements, which are already sorted. Then the merges build the answer back up.

The picture shows both phases on our example.

split38 27 43 3 9 82 1038 27 433 9 82 103827 433 982 10382743398210size 1merge3827 433 910 8227 38 433 9 10 823 9 10 27 38 43 82
Blue: the list is split in half again and again. Purple: every piece is a single element, already sorted. Green: neighbouring sorted pieces are merged, each merge taking the smaller front each time. Amber: the final merge gives the sorted list.

The splitting does no real work. It only decides the pieces. All the sorting happens in the merges on the way back up.

The solution ​

python
def merge_sort(nums: list[int]) -> list[int]:
    if len(nums) <= 1:                     # (1)
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])          # (2)
    right = merge_sort(nums[mid:])
    return merge(left, right)              # (3)

def merge(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:                   # (4)
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])                      # (5)
    out.extend(b[j:])
    return out

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # → [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([]))                           # → []
print(merge_sort([5, 5, 1]))                    # → [1, 5, 5]

(1) The base case. Zero or one element is already sorted. Without this line, the recursion would never stop.

(2) Sort each half by calling merge_sort on it. Trust that it returns a sorted list. This is Move 5 from 4.0.0: solve a smaller copy of the same problem.

(3) Combine the two sorted halves into one sorted list.

(4) On a tie, take from the left half. Values from the left half started earlier in the list, so equal values keep their original order. This makes merge sort stable. Writing < here would still sort correctly, but equal values from the right would jump ahead, and it would no longer be stable.

(5) When one half runs out, the rest of the other half is already sorted and bigger than everything taken. Copy it on.

Complexity, worked out ​

How many levels? Each split halves the size. Starting from n, how many halvings reach 1? That is the number of times you can divide n by 2, which is \log_2 n. For a million elements, about 20 levels.

How much work per level? Look at any one level of merges. Together, the merges on that level handle every element exactly once. On the second-to-last level of the picture, the four merges together touch all 7 numbers. So each level costs O(n).

Total: \log_2 n levels times n work per level gives O(n \log n). Chapter 4.1 draws the same argument as a tree.

This is O(n \log n) in the best, average and worst case. The splits are always exact halves, whatever the data is. No input can make merge sort slow. That predictability is its main selling point.

For a million elements: n^2 is 10^{12} steps, about 15 minutes at typical speeds. n \log_2 n is about 2 \times 10^7, a fraction of a second.

Memory. The merge builds a new output list. The extra memory needed at any one moment is O(n). On top of that, the recursion keeps up to \log_2 n calls waiting on the stack. So merge sort is not in place. This is its main cost.

The version above also makes copies with every slice, nums[:mid] and nums[mid:]. That adds work but does not change the O(n \log n) total, since each level copies n elements in all. A tighter version passes start and end indexes and merges through one shared helper list, so it never slices.

python
def merge_sort_inplace(nums: list[int]) -> None:
    buf = [0] * len(nums)                       # (1) one helper list, reused

    def sort(lo: int, hi: int) -> None:         # sorts nums[lo:hi]
        if hi - lo <= 1:
            return
        mid = (lo + hi) // 2
        sort(lo, mid)
        sort(mid, hi)
        i, j, k = lo, mid, lo
        while i < mid and j < hi:
            if nums[i] <= nums[j]:
                buf[k] = nums[i]; i += 1
            else:
                buf[k] = nums[j]; j += 1
            k += 1
        while i < mid:
            buf[k] = nums[i]; i += 1; k += 1
        while j < hi:
            buf[k] = nums[j]; j += 1; k += 1
        nums[lo:hi] = buf[lo:hi]                # (2) copy the merged run back

    sort(0, len(nums))

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

(1) One helper list of size n, made once, instead of new lists at every level.

(2) After merging into the helper, copy the merged stretch back into nums.

CaseTime
BestO(n \log n)
AverageO(n \log n)
WorstO(n \log n)
Extra memoryO(n)
StableYes

Where merge sort wins ​

Linked lists. Merging two linked lists needs no extra memory. You just relink the nodes. And merge sort never needs to jump to a random position, which linked lists cannot do quickly. So merge sort is the standard way to sort a linked list (LeetCode 148).

Data too big for memory. Say you must sort 100 GB of data, but the computer has only 8 GB of memory. Sort the data in 8 GB pieces. Save each sorted piece to disk. Then merge the pieces, reading only the front of each one. This is external sorting, and it is merge sort at heart. Databases do it when a query sorts more rows than fit in memory.

When stability matters. Python's built-in sort, Timsort, is a merge sort underneath, partly for this reason. Java uses a merge sort for sorting objects for the same reason.

Counting inversions: the classic follow-up ​

An inversion is a pair that is out of order: a bigger value before a smaller one. Counting them measures how unsorted a list is. A music app could compare your ranking of ten songs with a friend's by counting how many pairs you rank differently.

The slow way checks every pair, O(n^2). Merge sort can count them for free, in O(n \log n). Look at the moment in a merge when we take a value from the right half. Some values from the left half are still waiting. Each of them is bigger than this value. Each of them also came before it in the original list. So each one makes an inversion with it. There are len(a) - i of them.

python
def count_inversions(nums: list[int]) -> tuple[list[int], int]:
    if len(nums) <= 1:
        return nums, 0
    mid = len(nums) // 2
    left, inv_left = count_inversions(nums[:mid])
    right, inv_right = count_inversions(nums[mid:])
    out, i, j, inv = [], 0, 0, inv_left + inv_right
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
            inv += len(left) - i            # every waiting left value is bigger
    out += left[i:] + right[j:]
    return out, inv

print(count_inversions([2, 4, 1, 3, 5])[1])   # → 3

The three inversions are (2, 1), (4, 1) and (4, 3).

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Show where O(n \log n) comes from." The list is cut in half again and again, which gives about \log_2 n levels. On each level, the merges together touch every element once, which is n work. So the total is n \log n.

"What is the worst case?" Also O(n \log n). The splits are always exact halves, whatever the data is.

"How much extra memory does it use?"O(n) for the merging, plus about \log n for the recursive calls. Saying only "O(\log n)" is a common mistake.

"Is it stable? Which line makes it stable?" Yes. The <= in the merge takes from the left half when values are equal.

"Why is merge sort good for linked lists?" Merging linked lists needs no extra memory, and merge sort never needs to jump to a random position.

"Count the inversions in a list." Do it inside the merge. When you take a value from the right half, every value still waiting in the left half is bigger than it. Add len(left) - i to the count.

One thing to volunteer: "Merge sort does all its work when merging. Quicksort does all its work when splitting. They are opposites."

Next: 4.0.28 Quick Sort. Usually the fastest sort in practice, and the one kind of input that makes it slow.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet