Merge sort

In 1945, John von Neumann sat at the University of Pennsylvania's Moore School, staring at blueprints for the EDVAC—a machine that didn't yet exist. He needed to prove its design would work, so he chose the most fundamental computational task: sorting data. The result was merge sort, the first algorithm ever written for a stored-program computer.

Merge sort couldn't have emerged earlier—it required three converging streams. First, the stored-program computer concept from von Neumann's famous 1945 "First Draft of a Report on the EDVAC," where instructions and data share memory. Second, WWII's ballistics calculations made sorting an urgent military necessity. Third, von Neumann himself understood both mathematics and machine limitations.

Von Neumann's 23-page manuscript detailed "meshing"—the merging routine at the heart of merge sort. The algorithm divides data recursively, sorts the pieces, then merges them back together. A 1948 report with Herman Goldstine made it one of the first algorithms to receive rigorous computational analysis.

Merge sort introduced computing to divide-and-conquer—break a problem into smaller subproblems, solve them independently, combine solutions. This approach matched how computers naturally work: subproblems are independent, so they can run on separate processors. Merge sort achieves O(n log n) performance in all cases—asymptotically optimal for comparison-based sorting.

Most immediately, merge sort solved external sorting—datasets too large for memory. Sort data in memory-sized chunks, write to disk, merge sorted chunks. This became foundational for database systems, payroll processing, any application requiring sorted records. Modern databases still use merge sort variants for merge joins and indexing. Every computer science curriculum teaches merge sort because it elegantly illustrates recursion, complexity analysis, and the paradigm that spawned binary search, quicksort, and Fast Fourier Transform.