Merge Sort
Merge Sort और Divide-and-Conquer
Merge sort sequence को दो ranges में बांटता, दोनों को recursively sort करता और फिर sorted results merge करता है। Zero या one-element range base case है। Reverse input पर भी time Θ(n log n) रहता है।
- Midpoint पर divide करें।
- Left और right range sort करें।
- दोनों ordered ranges combine करें।
Recursion और bubble sort से तुलना करें।
Recursive Trace
[38 27 43 3 9 82 10]
left [38 27 43] → [27 38 43]
right [3 9 82 10] → [3 9 10 82]
final merge → [3 9 10 27 38 43 82]Splitting order नहीं बनाता; returning recursion में sorted child ranges का merge actual ordering करता है।
Merge Procedure
Left, right और buffer के indices रखें। छोटे front element को buffer में copy करें, उस index को आगे बढ़ाएं, फिर बचा tail copy करें। Equal values पर left पहले लेने से stability रहती है।
Complete C++ Program
void merge_sort_range(std::vector<int>& a,
std::vector<int>& temp,
std::size_t left, std::size_t right) {
if (right - left < 2) return;
auto mid = left + (right - left) / 2;
merge_sort_range(a, temp, left, mid);
merge_sort_range(a, temp, mid, right);
merge(a, temp, left, mid, right);
}ऊपर English section का complete compile-ready program एक reusable buffer लेता है। Half-open ranges off-by-one errors कम करती हैं।
Correctness और Stability
Induction से: length 0/1 range sorted है। Recursive calls छोटी ranges sort करती हैं। Merge हर बार least unconsumed front चुनता है, हर element exactly once copy करता है; इसलिए ordered permutation मिलता है। Equal keys पर left पहले चुनने से original relative order बचता है।
Time और Space
| Property | Result |
|---|---|
| Best/Average/Worst | Θ(n log n) |
| Buffer | Θ(n) |
| Recursion depth | Θ(log n) |
| Stable | हाँ, left-first tie |
हर level में total merge work linear और levels logarithmic हैं।
Use Cases और Comparison
Stable order और predictable performance में merge sort अच्छा है। General vector के लिए std::sort, standard stable sorting के लिए std::stable_sort लें। External sorted runs और linked structures में merge pattern natural है। STL algorithms देखें।
Mistakes, Testing और Practice
- Base case जरूर रखें।
- Inclusive और exclusive bounds mix न करें।
- Left/right leftover tail copy करें।
- हर recursion में नया buffer न बनाएं।
- Duplicates से stability test करें।
Empty, odd/even length, sorted, reverse और negative inputs test करें। Bottom-up merge sort practice करें।
Authoritative संदर्भ
Algorithm definition और complexity authoritative sources से verify किए गए हैं।
