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〉.