Merge Sort

Merge sort is a sorting technique based on the divide and conquer technique.

Merge Sort

Recursively: split the list in half, sort each half, then merge the sorted halves together.

Algorithm :

MergeSort(A, p, r):
    if p > r 
        return
    q = (p+r)/2
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

Example :

30 64 26 46 109 21 84 98
30 64 26 46 21 109 84 98
26 30 46 64 21 84 98 109
21 26 30 46 64 84 98 109

Notes :

1. It is divide and conquer technique.
2. It uses merge procedure which combine two sorted lists into one sorted list in O(N) time complexity.
3. The merge procedure (which is used by merge sort) is outplace technique, it has O(N) time complexity, but if we use in-place merge procedure this would have O(N^2) time complexity.
4. That’s why merge algorithm has O(N log N) time complexity (in all cases).
5. In-pace merge sort Recurrence relation :

   T(N) = 2T(N/2) + O(N) = O(N log N) 

6. If we use outplace merge procedure in merge sort, then recurrence relation relation of merge sort :

   T(N) = 2T(N/2) + O(N^2) = O(N^2) 

7. Merge sort is out-place but stable sorting algorithm.
8. It has O(N) space complexity and auxiliary.

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.