Merge Sort in DSA – Complete Guide

📌 What is Merge Sort?

Merge Sort ek Divide and Conquer algorithm hai 👇

👉 Array ko chhote parts me divide karta hai
👉 Phir unko sort karke merge karta hai

---

⚙️ How Merge Sort Works

Step-by-step:

1. Array ko 2 halves me divide karo
2. Har half ko recursively sort karo
3. Dono sorted halves ko merge karo
4. Final sorted array milta hai

---

📊 Example (Dry Run)

Array:
[38, 27, 43, 3, 9, 82, 10]

---

Step 1: Divide

[38,27,43,3]     [9,82,10]

---

Step 2: Divide Again

[38,27] [43,3]   [9,82] [10]

---

Step 3: Single Elements

[38] [27] [43] [3] [9] [82] [10]

---

Step 4: Merge (Sorted)

[27,38] [3,43]   [9,82] [10]

---

Final Merge:

[3,27,38,43] + [9,10,82]
➡️ [3,9,10,27,38,43,82]

---

💻 Merge Sort in PHP (Code Example)

<?phpfunction mergeSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }    $mid = intdiv(count($arr), 2);    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);    $left = mergeSort($left);
    $right = mergeSort($right);    return merge($left, $right);
}function merge($left, $right) {
    $result = [];    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] < $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }    return array_merge($result, $left, $right);
}// Example
$array = [38, 27, 43, 3, 9, 82, 10];
$sortedArray = mergeSort($array);print_r($sortedArray);?>

---

⚡ Key Insight

👉 Merge Sort me divide + merge = sorting
👉 Recursion ka heavy use hota hai

---

⏱️ Time & Space Complexity

Case	Time Complexity
Best Case	O(n log n)
Average	O(n log n)
Worst Case	O(n log n)

Space Complexity:
👉 O(n) (extra memory required)

---

👍 Advantages

• Fast & efficient (O(n log n))
• Stable sorting algorithm
• Large datasets ke liye best

---

👎 Disadvantages

• Extra memory use karta hai
• Recursive calls (stack usage)
• Simple algorithms se complex

---

🎯 When to Use Merge Sort?

• Large datasets
• Stable sorting required ho
• Linked list sorting
• External sorting (files, big data)

---

🔥 Merge Sort vs Quick Sort

Feature	Merge Sort	Quick Sort
Time Complexity	O(n log n)	O(n log n) avg
Worst Case	O(n log n)	O(n²)
Space	O(n)	O(log n)
Stability	✅ Yes	❌ No

---

🚀 Conclusion

Merge Sort ek powerful aur efficient algorithm hai jo large data aur stable sorting ke liye best choice hai. Ye DSA me ek must-learn concept hai, especially interviews ke liye.