merge sort

Also known as mergesort, MergeSort

worst-case optimal stable divide and conquer comparison sorting algorithm

Key facts

Class: Sorting algorithm
Data structure: Array
Worst case performance: O ( n log ⁡ n ) {\displaystyle O(n\log n)}
Best case performance: Ω ( n log ⁡ n ) {\displaystyle \Omega (n\log n)} typical, Ω ( n ) {\displaystyle \Omega (n)} natural variant
Average performance: Θ ( n log ⁡ n ) {\displaystyle \Theta (n\log n)}
Worst case space complexity: O ( n ) {\displaystyle O(n)} total with O ( n ) {\displaystyle O(n)} auxiliary, O ( 1 ) {\displaystyle O(1)} auxiliary with linked lists

via Wikipedia infobox

Wikidata facts

Image: Merge sort algorithm diagram.svg

Show 3 more facts

Stack Exchange tag: stackoverflow.com/tags/mergesort
Commons category: Merge sort
time of discovery or invention: 1945-00-00

Sources (5)

via Wikidata · CC0

~36 min read

Article

In computer science, merge sort (also commonly spelled as mergesort or merge-sort) is an efficient and general purpose comparison-based sorting algorithm. Most implementations of merge sort are stable, which means that the relative order of equal elements is the same between the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.

Algorithm