merge sort
Sign in to saveworst-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
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