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.

Merge sort procedure
Input : A an array in the range 1 to n.
Output : Sorted array A.

Procedure MERGESORT (A,l,r)
1.   if l < r
2.    	then q ← (l+r )/2 
3.    		MERGESORT (A,l,q)
4.  		MERGESORT (A,q+1, r)
5.  		MERGE (A,l,q,r)

Merge procedure (Algorithm 1)

Procedure MERGE (A,l,q,r)
1.  i ← l
2.  j ← q+1
3.  k ← 0
4.  while (i ≤ q) and ( j ≤ r) do
5.   	 k  ← k+1
6.  	 if A[i] ≤ A[j] then
7.  		 TEMP [k] ← A [i]
8.  		 i ← i +1
9.  	 else
10.  		 TEMP [k] ← A [j]
11.  		 j ← j +1
12. if j > r  then 
13.   	 for t ←0 to q – i do
14. 		 A [r-t] ← A [q-t]
15.  for t ← 0 to k-1 do
16. 	 A [l +t] ← TEMP [t+1]

Merge procedure (Algorithm 2)

MERGE(A, p, q, r)
	1 	n1 ← q - p + 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[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

Analysis of Merge Sort
To find the middle of the sub array will take D(n)=(1).
To recursively solve each sub problem will take 2T(n/2).
To combine sub arrays will take (n).

Therefore T(n)=T(n/2)+ (n) + (1)
We can ignore (1) term.

The operation of merge sort on the array A = 〈5, 2, 4, 7, 1, 3, 2, 6〉.