3.9.5 Merge Sort

Knowledge Base > Algorithm > Sorting

Overview

Merge Sort is a O(n⋅lgn) comparison-based sorting algorithm, and is an example of divide and conquer strategy (of method 3.7.3.1).

Algorithm

Pseudocode

Merge-Sort(A,p,r)

1 if p < r 2    then q ←⌊(p + r)∕2⌋ 3       Merge-Sort(A,p,q) 4       Merge-Sort(A,q + 1,r) 5       Merge(A,p,q,r)

Merge(A,p,q,r)
 

1 n1 ← p - q + 1 2 n2 ← r - q 3   ⊴ create arrays L[1…n1 + 1] and R[1…n2 + 1] 4 for i ← 1 to n1 5 do L[i] ← A[p + i - 1] 6 for j ← 1 to n2 7 do R[i] ← A[q + j] 8 L[n1 + 1] ←∞ 9 R[n2 + 1] ←∞ 10 i ← 1 11 j ← 1 12 for k ← p to r 13 do if L[i] ≤ R[j] 14          then A[k] ← L[i] 15             i ← i + 1 16          else A[k] ← R[j] 17             j ← j + 1

Conceptually, the algorithm recursively splits the list to be sorted into two groups, until we have each sub-list size of length 1, in which case the list itself is returned. Next,merges the two sublists into a sorted sequence.

Loop Invariant
Statement
At the start of each iteration of the loop in lines 12-17, the subarray A[p…k - 1] contains the k - p smallest elements of L and R in sorted order. Also L[i] and R[j] are the smallest elements of L and R that have not been copied back into A.
Initialization
Before the 1^st iteration of the lop, we have k = p. So the subarray A[p…k - 1] contains 0 smallest element of L and R. And since, i = j = 1, both L[i] and R[j] are the smallest elements of the arrays that have not been copied into A. And both L are R are sorted.
Maintenance
Suppose L[i] ≤ R[j], then L[i] is the smallest element not copied into A. Since A[p…k - 1] is k - p smallest elements, L[i] is (k - p + 1)^th smallest element. So, line 14 copies L[i] into A[k],A[p…k] contains k - p + 1 smallest elements. Incrementally, k + i give loop invariant. If L[i] > R[j], then lines 16, 17 perform the appropriate action to maintain loop invariant.
Termination
When, k = r + 1, A[p…k - 1] = A[p…r] contains k - p smallest element in sorted order. This gives, k - p = r + 1 - p smallest elements in sorted order. The arrays L and R together contains n₁ + n₂ + 2 = r -p + 3 elements, all but the two largest ∞ have been copied back into A.

Thus, prove the correctness of Merge-Sort.

Time Complexity

If the running time of merge sort for a list of length n is T(n), then the recurrence function is defined as follow:

The total is cn ⋅ lg n + cn
T(n) = n ⋅ T(1) + cn ⋅ lg n = Θ(n ⋅ lg n)
Next, we apply divide and conquerer method (of method 3.7.3.1) to solve the recurrence,

Space Complexity

Merge sort does not sort in place, meaning that the memory size of the input must be allocated for the sorted output to be stored in whenever the merge operation is performed. For each level of divide-and-conquer procedure, an extra space of O(2n) is needed, and the height of the recursive tree is lg n. Thus, a total of O(n⋅ lg n) extra space is used. However, sorting in-place is possible but complicated, and will offer little performance gains in  practice (even it still runs at Θ(n ⋅ lg n) time).

Stability

Merge Sort is stable, meaning it preserves the input order of equal elements in the sorted output. After comparison, this method put the current element, left[i] or right[j], into a right position, A[k], in sorted list. This preserve the same order of occurrence for two duplicated elements after the list is sorted, because the identical elements in the left sublist has is created earlier than elements in the right sublist. However, if the relational test remove equality relation, the order of occurrence for the same elements is reversed.

Source Code

• Merge Sort (C)