Merge sort
A stable, divide-and-conquer sorting algorithm invented by John von Neumann.
Merge sort (also written mergesort or merge-sort) is a comparison-based sorting algorithm that works well on many kinds of data. It is stable in most implementations, so items with equal values keep the same relative order from input to output. The algorithm uses a divide-and-conquer approach and was created by John von Neumann in 1945. A detailed explanation of the bottom-up version appeared in a 1948 report by Goldstine and von Neumann.
The basic idea is to split the unsorted list into n sub-lists, each with one element (a single-element list is already sorted). Then, repeatedly merge these sub-lists into new sorted sub-lists until only one sub-list remains—that is the sorted result. Merging two already-sorted sub-lists can be done in linear time, which makes the whole process efficient.
In a top-down implementation, the algorithm recursively splits the list into smaller pieces (called runs) until each piece has size 1, then merges them back together. To avoid extra copying, the direction of merging alternates with each recursion level. For example, with two elements, they are copied to a temporary buffer and merged back. With four elements, single-element runs from the original array are merged into the buffer, then those two-element runs are merged back to the original array, and so on.
A bottom-up implementation treats the list as an array of n sub-lists of size 1 and repeatedly merges them back and forth between two buffers. Another bottom-up approach uses a small fixed-size array of references to nodes, where each slot holds a list of size 2^i or nil. Nodes are merged into this array, then the array is merged into a single sorted list.
For a top-down list-based version, the algorithm checks if the list has zero or one element (the base case). If not, it divides the list into two equal halves, recursively sorts each half, and then merges the two sorted halves into a result list. The merge function compares the first elements of the two input lists, appends the smaller one to the result, and continues until one list is empty, then appends the remaining elements.
In terms of performance, sorting n items with merge sort takes O(n log n) comparisons in both the average and worst cases. This follows from the recurrence T(n) = 2T(n/2) + n, where T(n) is the number of comparisons for a list of length n. The worst-case number of comparisons is given by the sorting numbers, which are close to (n ⌈lg n⌉ − 2⌈lg n⌉ + 1), falling between (n lg n − n + 1) and (n lg n + n + O(lg n)). The best case requires roughly half as many iterations as the worst case.
- Inventor
- John von Neumann
- Field
- Computer science, sorting algorithms
- Type
- Comparison-based, divide-and-conquer
- Known for
- Efficient O(n log n) sorting, stability, and sequential data handling
Lore & Background
Merge sort is a comparison-based sorting algorithm that operates efficiently on general-purpose data. It was invented by John von Neumann in 1945, with a detailed description of the bottom-up variant appearing in a 1948 report by Goldstine and von Neumann. The algorithm follows a divide-and-conquer approach: it recursively splits an unsorted list into single-element sublists (each inherently sorted), then repeatedly merges these sublists in linear time to produce larger sorted sublists until one fully sorted list remains. Most implementations are stable, preserving the relative order of equal elements between input and output. Merge sort is well-suited to parallelization due to its divide-and-conquer structure, with variants including parallel recursion and K-way merging. It can also be optimized for modern memory hierarchies using cache-aware techniques, such as partitioning subarrays to fit within a CPU’s cache and sorting them with an in-place algorithm like insertion sort before completing the merge. For external sorting on tape drives, merge sort can be adapted to use multiple tapes and polyphase merging to minimize drive operations. The algorithm’s time complexity is efficient for large datasets, and its recursive or iterative implementations can be expressed in various programming languages, including C-like code and functional languages like Haskell.
Reader's Guide
Merge sort is significant as a foundational sorting algorithm with guaranteed O(n log n) average and worst-case performance. Its stability—preserving the relative order of equal elements—makes it preferable in many applications where data ordering matters beyond the sort key. The algorithm is particularly efficient for data that can only be accessed sequentially, making it popular in languages like Lisp. Merge sort uses approximately 39% fewer comparisons than quicksort in its worst case compared to quicksort's average case, and its worst-case complexity in terms of moves is O(n log n), matching quicksort's best case. However, most common implementations do not sort in place, requiring additional memory for the sorted output. The natural merge sort variant exploits naturally occurring runs in input data, making it the key component of Timsort. Merge sort's legacy endures as a standard algorithm taught in computer science and used in practice where stability and predictable performance are required.
Did You Know?
- Merge sort uses approximately 39% fewer comparisons than quicksort does in its average case.
- Natural merge sort is exploited as the key component of Timsort.
Frequently Asked Questions
What are Merge sort's powers and role?
It delivers a guaranteed O(n log n) running time in every case—best, average, and worst—so performance never degrades with an unlucky input. It is also stable, preserving the original relative order of equal keys, and it handles sequential structures like linked lists especially well.
How does Merge sort's story end?
The recursion bottoms out the moment a sub-list shrinks to zero or one element, which is trivially sorted. The calls then unwind, merging each pair of sorted halves upward until the full original array is reassembled in order.
Why is Merge sort important?
It was among the first practical algorithms to hit the O(n log n) lower bound for comparison-based sorting, showing that no such sort can be asymptotically faster. Its predictable speed and stability made it a default in early mainframe libraries, and it still appears in modern standard libraries and external-sorting systems.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record