Merge Sort

Merge Sort#

Contents#

Merge sort can be attributed to John Von Neumann around 1945.

Merge sort is a stable sorting algorithm, which means that duplicate elements retain the same relative ordering both before and after the sorting operation.

Merge sort is based on the idea of sorted array merge.

Divide

The input array is partitioned into two subarrays based on the array’s midpoint.

Conquer

Each subarray is recursively sorted. The base case occurs when a subarray contains a single element, at which point it is trivially sorted.

Combine

The resulting sorted subarrays are combined via SORTED_ARRAY_MERGE.

 INPUT    an array A[0:n - 1] of n values where n >= 1, l = 0, r = n - 1
OUTPUT    the array sorted in ascending order

MERGE_SORT(A, l, r)
 1    if l == r
 2        return A[l]
 3
 4    m  = l + (r - l) // 2
 5    a1 = MERGE_SORT(A, l    , m)
 6    a2 = MERGE_SORT(A, m + 1, r)
 7
 8    return SORTED_ARRAY_MERGE(a1, a2)

Correctness#

Base Case

  • Let \(|A| = 1\). \(A\) is trivially sorted and so mergesort is guaranteed to produce the correct result.

Inductive Step

  • Assume that mergesort produces the correct output for an array of size \(n/2\).

  • Then mergesort produces the correct output for an array of size \(n\) by sorting two arrays of size \(n/2\) and then combining them via sorted-merge.

Therefore mergesort is correct for an array of any size \(n\) since an array will be sub divided until it reaches the base case. The inductive step demonstrates that so long as mergesort is correct for some sub problem it is correct for all sub problems.

Complexity#

Time#

The time complexity of mergesort is \(T(n) = 2T(n/2) + \Theta(n)\) where the term \(2T(n/2)\) represents the number of sub problems times the cost of recursively sorting a sub problem and the term \(\Theta(n)\) is the cost of running the comparison operation. The comparison operation runs in linear time with respect to the combined size of the two input arrays. According to the Master Theorem the time complexity of mergesort becomes

\(a = 2, b = 2, d = 1 \implies \Theta(n \log n)\)

worst case \(T(n) = \Theta(n \log n)\)

Space#

Merge sort has space requirement \(S(n) = \Theta(n)\) due to the sorted-array merge operation.

mergesort doesn’t create any auxiliary data structures, and it only uses a constant number of variables. But there are two hidden costs:

  • the space cost associated with sorted-merge

  • the space cost of the recursive call stack

\(S(n) = S(n/2) + \Theta(n)\)

The first term is not \(2S(n/2)\) because sub problems are solved sequentially, one after the other, and so memory is only expended on a single sub problem at a time.

By the Master Theorem we see that \(a = 1, b = 2, d = 1 \implies (d = 1) \gt 0 = \log_{(b = 2)} (a = 1)\). In other words, the combination operation dominates the cost of solving the sub problems and so the space complexity of mergesort is \(\Theta(n^d) = \Theta(n^{(1)}) = \Theta(n)\).

Alternatively, we can think about the space complexity as follows. The call stack contains \(\Theta(\log n)\) stack frames because the size of the array reduces by half each recursive call and the recursive calls stop when \(n = 1\). In the worst case analysis, each stack frame requires \(O(n)\) space (but in reality most of them require less).

\(S(n) = \Theta(\log n) + \Theta(n) = \Theta(n)\)

There are versions of mergesort that do not require auxiliary arrays, but these versions tend to have the worst performance in practice.

Mergesort vs quicksort

Mergesort has a better worst-case time complexity than quicksort.

\( T(n) = \begin{cases} \Theta(n \lg n) & \text{mergesort} \\ \Theta(n^2) & \text{quicksort} \\ \end {cases} \)

However, quicksort performs as good as mergesort asymptotically in expectation.

\( T(n) = \begin{cases} \Theta(n \lg n) & \text{mergesort} \\ \Theta(n \lg n) & \text{quicksort} \\ \end {cases} \)

In practice, quicksort is usually the faster of the two sorting algorithms since the constraints associated with its time complexity are lower.

In comparison to quicksort, mergesort requires more auxiliary space.

\( S(n) = \begin{cases} \Theta(n) & \text{mergesort} \\ \Theta(\lg n) & \text{quicksort} \\ \end {cases} \)

Resources#

https://www.digitalocean.com/community/tutorials/merge-sort-algorithm-java-c-python

Contents