It closely follows the divide & Conquers paradigm.
Conceptually, it works as follows:
The Main purpose is to sort the unsorted list in nondecreasing order.
ALGORITHM-MERGE SORT 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)
The following figure illustrates the dividing (splitting) procedure.
FUNCTIONS: MERGE (A, p, q, r) 1. n 1 = q-p+1 2. n 2= r-q 3. create arrays [1.....n 1 + 1] and R [ 1.....n 2 +1 ] 4. for i ← 1 to n 1 5. do [i] ← A [ p+ i-1] 6. for j ← 1 to n2 7. do R[j] ← A[ q + j] 8. L [n 1+ 1] ← ∞ 9. R[n 2+ 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
In this method, we split the given list into two halves. Then recursively analyzing merge sort and dividing. We get many sorted lists.
At last, we combine the sorted lists.
Let T (n) be the total time taken in Merge Sort
So, the relational formula becomes
But we ignore '-1' because the element will take some time to be copied in merge lists.
So T (n) = 2T + n.........equation 1
Put 2 equation in 1 equation
Putting 4 equation in 3 equation
From Stopping Condition:
Apply log both sides:
log n=log2i
logn= i log2
=i
log2n=i
From 6 equation