Merge sort जो है वह divide & conquer तकनीक का प्रयोग करता है. divide & conquer तकनीक को जॉन नयूमन्न ने 1945 में प्रस्तावित किया था। divide & conquer एक ऐसी तकनीक है जिसमें डेटा की एक comlex (कठिन) list को sub-list में विभाजित कर लिया जाता है और इस प्रकार लिस्ट को तब तक विभाजित किया जाता है जब तक कि लिस्ट में केवल एक element बचें । इसके बाद इन sub-lists को sort करके combine कर दिया जाता है। merge sort को two way sort भी कहते है । merge sort की time complexity O( n log n) होती है जिस कारण merge sort को बहुत अच्छी algorithm समझा जाता है।
Merge Sort Example
यह एक unsorted array है:-
जैसा कि हम जानते है कि merge sort में सबसे पहले पूरे array को आधे भाग में विभाजित किया जाता है । हमारे पास इस array में 8 elements है तथा इस array को दो भागों में विभाजित किया जाता है जिसमें कि 4 – 4 elements होंगे ।
फिर इन दो arrays को भी दो भागों में विभाजित किया जाता है।
इसके बाद हम इन arrays को भी विभाजित कर देते है. इसके बाद लिस्ट में केवल एक elements बचेगा । जिसे विभाजित नहीं किया जा सकता है। अब हम इन सब को उसी प्रकार combine करेंगे जिस प्रकार की ये विभाजित हुए थे। सबसे पहले हम elements को प्रत्येक लिस्ट के लिए compare करते है तथा उसके बाद इन्हें sort करके combine कर दिया जाता है।
सबसे पहले 15 और 34 को compare करते है परन्तु ये तो पहले से ही sorted है. 30 और 12 को compare किया जाता है क्योंकि 30, 12 से बड़ा है इसलिए 12 को 30 से पहले लिखेंगे. 38 और 21 को compare करेंगे इसमें 21 को 38 से पहले लिखेंगे. 43 और 50 पहले से sorted है । अब हम दो elements वाली लिस्ट को compare करेंगे ।
इसके बाद अंत में इन दो लिस्ट को compare किया जाता है:-
Merge Sort Algorithm
इस sort की algorithm निम्नलिखित है:-
MERGE-SORT (A, p, r)
1. IF p<r
2. THEN q = FLOOR [(p+q)/2] ///divide step
3. MERGE (A, p, q) ///conquer step
4. MERGE (A, q+1, r) ///conquer step
5. MERGE (A, p, q, r) ///conquer step