Merge sort
A stable, divide-and-conquer sorting algorithm invented by John von Neumann.
Merge sort (also commonly spelled as mergesort or merge-sort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations of merge sort are stable, meaning the relative order of equal elements is preserved between input and output.
- 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
The algorithm works by dividing an unsorted list into n sub-lists, each containing one element (which is considered sorted), then repeatedly merging sublists to produce new sorted sublists until only one sublist remains. This process is efficient because merging and sorting two sublists can be performed in linear time, provided the sublists are already sorted.
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 25-38
Elsewhere in the Algorithms And Data Structures universe
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