Merge sort
worst-case optimal stable divide and conquer comparison sorting algorithm
Merge sort (or mergesort) is an divide and conquer algorithm for sorting a list of items. John von Neumann first presented it in 1945. It is similar to quicksort, developed in 1960. The difference is that with merge sort, dividing the lists is trivial, and merging them together isn't. With quicksort, dividing the lists is more complex, but the merging step is trivial.
Usage change
Merge sort is a stable sorting algorithm, while quicksort is not. It has a worst-case complexity of O(n*log(n)). Merge sort is also highly parallelizable. It can be used for solving the inversion counting problem.
Algorithm change
- If the list contains only one item, then return the list
- Divide the list into two lists of half the size of the list
- Apply the algorithm to each of the two lists
- Merge the two sorted lists together
