Merge sort:
The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.
Divide: Divide the n-element sequence to be sorted into two subsequences of n=2 elements each.
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.
The key operation of the merge sort algorithm is the merging of two sorted sequences in the “combine” step. We merge by calling an auxiliary procedure MERGE (A, p, q, r) where A is an array and p, q, and r are indices into the array such that p≤ q < r. The procedure assumes that the subarrays A (p…. q) and A (q+1……… r) are in sorted order. It merges them to form a single sorted subarray that replaces the current subarray A (p …….r). Our MERGE procedure takes time ϴ(n), where n = r- p+1 is the total number of elements being merged.
MERGE(A, p, q, r)
1 n1 ← q - p + 1
2 n2 ← r – q
3create 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[j] ← 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
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)
Analysis of Merge-sort
When we have n > 1 elements, we break down the running time as follows.
Divide: The divide step just computes the middle of the subarray, which takes constant time. Thus, D(n)=ϴ(1).
Conquer: We recursively solve two subproblems, each of size n/2, which contributes 2T(n/2) to the running time.
Combine: We have already noted that the MERGE procedure on an n-element subarray takes time ϴ(n) and so C(n)=ϴ(n).
The recurrence for the worst-case running time T(n) of merge sort: The solution for above recurrence is ϴ (n log n).