How Mergesort Works
Split the list in half, sort each half recursively, merge the two sorted halves. The first algorithm written for a stored-program computer.
What you will learn
- Why von Neumann's 1945 binary-merge insight made O(n log n) sorting tractable on early computers
- How the recursive split with a midpoint produces log-base-2 levels of work
- How the inner merge function pops the smaller front element from each sorted half
- Why result.extend(left) and result.extend(right) handle unequal-length halves without extra logic
- How the doctest pins the contract on duplicates, the empty list, and a reverse-sorted input
- Why mergesort is stable and Timsort builds directly on its merge step
- Where the O(n) auxiliary memory comes from and why quicksort avoids it
Prerequisites
- Comfort reading recursive Python
- Familiarity with list slicing syntax
- No prior knowledge of mergesort required
The story behind mergesort
John von Neumann described mergesort in 1945, in the First Draft of a Report on the EDVAC, which is the same document that defined the stored-program computer. He needed a sort that could run on a tape-based machine with no random access, and a binary merge of two sorted runs is one of the few sort steps that works in a single linear pass over each tape. That gave him an O(n log n) algorithm at a time when most published sorts were O(n squared).
The algorithm was so well suited to the machines of its era that it became the canonical example of divide and conquer in textbooks for the next half-century. Mergesort is also stable, meaning equal keys keep their input order, which matters for any sort that runs after another sort. Modern Python uses Timsort, written by Tim Peters in 2002, and Timsort is mergesort with a few extra rules: detect already-sorted runs, merge runs in a stack, and choose run sizes to keep cache pressure low. The merge step at the heart of Timsort is the same one von Neumann sketched on the EDVAC report.
Module Docstring and Run Instructions
sorts/merge_sort.py:1The module docstring identifies the algorithm and shows the doctest invocation for both python and python3 along with the manual run command.
A reader picks up the file expecting to know how to execute it before reading any logic, and the module docstring delivers exactly that. Line 2 names the algorithm in the same shape every sorts/ file uses. Lines 5 and 7 give two doctest commands because some systems still expose a python binary on Python 2 and others only ship python3; the redundancy is intentional. Line 9 shows the manual run command. There is no usage example or API description here because the function docstring further down owns that role. The split between module-level run instructions and function-level contract is one of the small consistencies that makes the catalog readable across 1,381 files.
Module docstrings carry run instructions. Function docstrings carry the contract and doctests. The split is consistent across every algorithm file.
"""
This is a pure Python implementation of the merge sort algorithm.
For doctests run following command:
python -m doctest -v merge_sort.py
or
python3 -m doctest -v merge_sort.py
For manual testing run:
python merge_sort.py
"""
The Signature, the Complexity Note, and the Doctest
sorts/merge_sort.py:13The function docstring states O(n log n) time and O(n) space, then pins the contract with three doctest examples.
A learner reading mergesort wants two facts before the code: how it scales and what its contract is. Lines 20 and 21 deliver the first by stating O(n log n) time and O(n) space outright, which is unusual in this repository (most files leave complexity for the reader to derive) and useful here because the space cost is the trade-off that distinguishes mergesort from quicksort. The three doctests then pin the contract end to end. merge_sort([0, 5, 3, 2, 2]) proves duplicates are preserved in order. merge_sort([]) proves the base case returns the empty list. merge_sort([-2, -5, -45]) proves a fully reverse-sorted negative list is no special case for the algorithm.
The signature is plain. The docstring states O(n log n) time and O(n) space and pins the contract with three doctests covering duplicates, empty input, and reverse-sorted negatives.
def merge_sort(collection: list) -> list:
"""
Sorts a list using the merge sort algorithm.
:param collection: A mutable ordered collection with comparable items.
:return: The same collection ordered in ascending order.
Time Complexity: O(n log n)
Space Complexity: O(n)
Examples:
>>> merge_sort([0, 5, 3, 2, 2])
[0, 2, 2, 3, 5]
>>> merge_sort([])
[]
>>> merge_sort([-2, -5, -45])
[-45, -5, -2]
"""
The Inner Merge: Pop the Smaller Front
sorts/merge_sort.py:32Walk both sorted lists, pop the smaller front each step. Two extend calls drain whichever list has leftovers.
The merge step is the heart of the algorithm and is what makes the divide-and-conquer split worth doing. Line 41 starts the merge with an empty result list and walks while both inputs still have elements. Line 42 is the only comparison: pop the smaller front element from left if its head is at most right's head, otherwise pop from right. Because both inputs are already sorted, the smaller front is the smallest element overall and goes next in result. Lines 43 and 44 then drain whichever list still has elements after the loop exits, and one of those two extends will always be a no-op. The merge runs in O(n) on n total elements and uses O(n) auxiliary memory.
Merge is one comparison per output element. The two extend calls drain whichever input still has elements after the loop, so unequal-length halves need no extra logic.
def merge(left: list, right: list) -> list:
"""
Merge two sorted lists into a single sorted list.
:param left: Left collection
:param right: Right collection
:return: Merged result
"""
result = []
while left and right:
result.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
result.extend(left)
result.extend(right)
return result
The Recursive Split: Base Case and Two Halves
sorts/merge_sort.py:47A list of length zero or one is already sorted. Otherwise split at the midpoint, recurse on each half, and merge the two sorted halves.
The recursion fits in four lines. Lines 47 and 48 are the base case: a list of length zero or one is already sorted, so return it unchanged and stop the recursion. Line 49 picks the midpoint with integer division. Line 50 is the divide-and-conquer step in one expression: recursively sort the left half (collection[:mid_index]), recursively sort the right half (collection[mid_index:]), and feed both sorted halves into the inner merge defined above. The recursion tree has depth log-base-2 of n, each level merges n total elements in O(n), and the multiplication is where the O(n log n) time complexity comes from. The slicing also explains the O(n) auxiliary memory: each recursive call allocates two new sublists.
Split at the midpoint, recurse on each half, merge. The recursion depth is log-base-2 of n; each level does O(n) work; the auxiliary memory comes from the slicing.
if len(collection) <= 1:
return collection
mid_index = len(collection) // 2
return merge(merge_sort(collection[:mid_index]), merge_sort(collection[mid_index:]))
The __main__ Guard Runs the Doctests
sorts/merge_sort.py:53The __main__ block first runs doctest.testmod() to validate the docstring examples, then drops into an interactive driver below.
Some algorithm files in the repository skip a manual driver. This one does not, but it does something interesting first: line 56 runs doctest.testmod() the moment the script is invoked directly, which means executing python3 merge_sort.py validates the in-file doctests before the interactive prompt appears. Compare this with sorts/quick_sort.py, which has no such call and relies entirely on CI to run its doctests. The choice here is friendlier to a contributor poking at the file in isolation: a doctest failure surfaces immediately on local run instead of waiting for the GitHub Actions build. Line 54 imports doctest from the standard library at run time so it is not loaded when the module is imported.
Calling doctest.testmod() inside __main__ runs the in-docstring examples on every direct invocation, so a contributor catches drift locally before pushing.
if __name__ == "__main__":
import doctest
doctest.testmod()
Interactive Driver with Input Validation
sorts/merge_sort.py:58A try/except around the input parse rejects non-integer tokens with a friendly message instead of an unhandled ValueError.
The interactive driver does what the contribution checklist requires: it reads input, sorts it, prints the result, and handles bad input with a Python exception rather than a crash. Line 60 strips trailing whitespace from the user input before splitting on commas because the contribution guide explicitly bans bare input() calls. Line 60's list comprehension calls int(item) on every token, which raises ValueError on any non-integer string. The try/except on lines 58 and 63 catches that ValueError and prints a clear message instead of a stack trace. Line 62 prints the sorted result with commas instead of Python's default list repr, which makes the output round-trippable with the next run. This is the canonical shape for an algorithm file's standalone driver.
Stripping the input, catching ValueError, and printing comma-separated output makes the driver round-trip cleanly. The contribution guide requires this shape.
try:
user_input = input("Enter numbers separated by a comma:\n").strip()
unsorted = [int(item) for item in user_input.split(",")]
sorted_list = merge_sort(unsorted)
print(*sorted_list, sep=",")
except ValueError:
print("Invalid input. Please enter valid integers separated by commas.")
You've walked through 6 key areas of the The Algorithms - Python codebase.
Continue: How Quicksort Works → Browse all projectsCreate code tours for your project
Intraview lets AI create interactive walkthroughs of any codebase. Install the free VS Code extension and generate your first tour in minutes.
Install Intraview Free