Merge Sort Algorithm (Divide and Conquer Approach)

Merge Sort ek highly efficient, comparison-based sorting algorithm hai jo Divide and Conquer algorithmic design paradigm par completely based hai. Iska worst-case time complexity guaranteed O(n log n) hota hai.

Divide and Conquer Steps

1. Divide: Array ko tab tak recursively do equal halves me divide karte hain jab tak har subarray me sirf 1 element na bache (single element array by default sorted hota hai).
2. Conquer: Subarrays ko recursively sort karte hain.
3. Combine (Merge): Do already sorted subarrays ko compare karke ek single consolidated sorted array me merge karte hain.

Divide Phase:
                      [ 38, 27, 43, 3, 9, 82, 10 ]
                             /            \
                   [ 38, 27, 43, 3 ]     [ 9, 82, 10 ]
                      /        \            /      \
                  [38, 27]   [43, 3]      [9, 82]  [10]
                   /    \     /    \       /   \     |
                 [38]  [27] [43]   [3]   [9]  [82]  [10]

Merge Phase:
                 [27, 38]     [3, 43]     [9, 82]   [10]
                     \           /            \      /
                   [ 3, 27, 38, 43 ]        [ 9, 10, 82 ]
                             \                /
                      [ 3, 9, 10, 27, 38, 43, 82 ]

Merge Procedure Algorithm

MERGE(A, low, mid, high)
1. n1 = mid - low + 1,  n2 = high - mid
2. Create temp arrays L[n1] and R[n2]
3. Copy data to L and R
4. Initialize i = 0, j = 0, k = low
5. While i < n1 and j < n2 do:
6.     If L[i] <= R[j] then:
           A[k] = L[i]; i = i + 1
       Else:
           A[k] = R[j]; j = j + 1
       k = k + 1
7. Copy remaining elements of L and R into A

Recurrence Relation and Complexity

Merge sort ki recurrence equation:

T(n) = 2T(n/2) + Θ(n)

Master Theorem (Case 2: a = 2, b = 2, f(n) = n => n^(log2 2) = n) apply karne par:

• Time Complexity: O(n log n) Best, Average aur Worst tino cases me!
• Space Complexity: O(n) auxiliary space temp arrays ke liye (Merge sort in-place nahi hota).
• Stability: Stable sorting algorithm.

Agli post me hum cover karenge Quick Sort Algorithm and Partitioning Methods.