# Merge Sort — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/merge-sort

> Array को आधा बाँटें, हर आधा sort करें, फिर merge करें — O(n log n) गारंटीशुदा।

## बाँटें, sort करें, merge करें

तब तक बाँटें जब हर टुकड़े में एक तत्व हो (स्वतः sorted)। फिर बार-बार दो sorted lists को उनके आगे की तुलना करके **merge** करें। `log n` स्तर विभाजन × हर स्तर merge को `O(n)` कार्य = `O(n log n)`, हमेशा।

## कार्यान्वयन

Merge चरण दिल है: दो sorted हिस्सों पर चलते दो इंडेक्स।

```python
def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(l, r):
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            out.append(l[i]); i += 1
        else:
            out.append(r[j]); j += 1
    out.extend(l[i:]); out.extend(r[j:])
    return out
```

## ट्रेड-ऑफ

फ़ायदे: पूर्वानुमेय `O(n log n)`, **stable**, linked list और बाहरी (disk) sorting के लिए बढ़िया। नुकसान: merge buffer को `O(n)` अतिरिक्त स्थान चाहिए।

**Quiz:** Merge sort का worst-case समय है...

- [ ] O(n^2)
- [x] O(n log n)
- [ ] O(n)

*Answer:* O(n log n). विभाजन हमेशा संतुलित होता है, इसलिए हर मामले में O(n log n) — quicksort के विपरीत।