MergeSort
From CS315
Written by Ben Pauling
MergeSort is one of the many sorting algorithms used in computer programming.
Contents |
Efficiency
Time - O(n log n)
Space - depends, can be anything from O(log n), O(n), and O(n log n)
Stability - MergeSort is stable.
Algorithm
MergeSort uses recursion to break down the list to be sorted into two seperate lists, continuing until there are n lists, each containing one element.
Since a list of one element is sorted, MergeSort then "merges" the lists back together, sorting them in much smaller pieces, eventually creating a fully sorted list.
Analysis
MergeSort has no practical difference between it's average and worst cases, it will always run in O(n log n) time.
In terms of space, the implementation of the sort as well as what is being sorted determines the space usage. It is possible to create an in-place MergeSort, but if space is an issue it would be better to use a different algorithm such as HeapSort.
Provided it is implemented correctly, MergeSort will always be stable, and never switch the position of an element with the same value as it merges the lists back together.
MergeSort is more efficient than Quicksort when the data to be sorted is most efficiently accessed sequentially.
MergeSort almost always makes fewer comparisons than Quicksort, with the only exception occurring when Quicksort obtains it's best case and MergeSort it's worst.
MergeSort is a good choice for sorting linked lists, as it is actually possible to create an algorithm with O(1) or constant space. Quicksort and Heap Sort are either inefficient or even impossible to code for this data structure.
Notes on Merge
The merge algorithm used to combine the sorted and divided lists is a relatively simple one. Merge outputs the smallest data item at each step, so that given several sorted lists, it will return a sorted list with all of the elements of the two input lists.
The time required is proportional to the sum of the lengths of the input lists.
This method works on the premise that sorting two sorted lists is much faster than two unsorted lists, as, among other things, you are only required to traverse eaxch list once.
Optimization
It is possible to create a MergeSort algorithm that only creates one extra array, by switching the target array from the original to the copy and back.
This version of the algorithm iteratively increases the amount of elements that the list is sorting, while swapping the original list with the copy as the destination and vice versa each time.
The end result will be the same as other algorithms for MergeSort, the orignal list completely sorted.
This implementation is much faster than the basic MergeSort algorithm.
