मर्ज सॉर्ट

मर्ज सॉर्ट एक कठिन समस्या को कई आसान समस्याओं में बदल देता है: दो सॉर्ट की हुई सूचियों को एक में जोड़ना आसान है। सूची को तब तक आधा करें जब तक हर टुकड़ा एक ही मान न रह जाए, फिर टुकड़ों को वापस मर्ज करें। यह क्लासिक डिवाइड एंड कॉन्कर एल्गोरिदम है, और इनपुट कुछ भी हो, इसका समय n log n होता है।

एक सूची के दो सॉर्ट हुए आधे हिस्से बफ़र वाली पंक्ति में, और छोटा सबसे आगे का मान वापस ऊपर सूची में जाता हुआ
एक सूची के दो सॉर्ट हुए आधे हिस्से बफ़र वाली पंक्ति में, और छोटा सबसे आगे का मान वापस ऊपर सूची में जाता हुआ

मूल विचार

मर्ज करना आसान हिस्सा है। अगर दो सूचियाँ हों जो अलग-अलग सॉर्ट हैं, तो उनके पहले मानों की तुलना करें और छोटा लें। फिर नए पहले मानों की तुलना करें और फिर से छोटा लें। जब एक सूची खत्म हो जाए, तो दूसरी का बाकी हिस्सा जोड़ दें। हर चरण एक मान लेता है, इसलिए कुल लंबाई m वाली दो सूचियों को मर्ज करने में ज़्यादा से ज़्यादा m − 1 तुलनाएँ लगती हैं। मर्ज सॉर्ट इसी से सॉर्ट करता है: सूची को आधा करें, हर आधे को मर्ज सॉर्ट से सॉर्ट करें, और दोनों आधे मर्ज करें।

एक उदाहरण

5, 1, 4, 2, 8 लें। इसे 5, 1 और 4, 2, 8 में बाँटें। पहला आधा 5 और 1 में बँटता है, जो मर्ज होकर 1, 5 बनते हैं। दूसरा आधा 4 और 2, 8 में बँटता है; 2, 8 को 2 और 8 से मर्ज किया जाता है, फिर 4 के साथ मर्ज होकर 2, 4, 8 बनता है। आख़िर में 1, 5 और 2, 4, 8 मर्ज होते हैं: 1, फिर 2, फिर 4, फिर 5, और 8 बच जाता है। यानी 8 तुलनाएँ, 12 लेखन और 4 मर्ज।

n log n क्यों

हर बँटवारा टुकड़ों को आधा करता है, इसलिए लगभग log₂ n स्तरों के बाद हर टुकड़ा एक ही मान रह जाता है। वापस ऊपर आते समय, मर्ज का हर स्तर हर मान को एक बार संभालता है, यानी हर स्तर पर n लेखन और n से कम तुलनाएँ। कुल मिलाकर यह लगभग n log₂ n है। 40 मानों के लिए सॉर्ट 216 लेखन और ज़्यादा से ज़्यादा 177 तुलनाएँ करता है; उसी सूची के लिए बबल सॉर्ट को 780 तुलनाएँ लग सकती हैं। इनपुट के क्रम का असर भी उन सॉर्ट से बहुत कम है: 40 मानों के लिए सॉर्ट की हुई सूची में 100 तुलनाएँ, उल्टी सूची में 116, और रैंडम सूची में लगभग 160 लगती हैं।

बफ़र, और स्थिरता

सूची में पास-पास रखे दो आधे हिस्सों को मर्ज करने के लिए, आम तरीका उन्हें बफ़र में कॉपी करके क्रम से वापस लिखना है। ऐप उस बफ़र को बार की दूसरी पंक्ति के रूप में दिखाता है। इसके लिए सूची जितनी अतिरिक्त मेमोरी चाहिए, और यही मर्ज सॉर्ट की मुख्य कीमत है। बदले में सॉर्ट स्थिर होता है: जब दोनों सबसे आगे के मान बराबर हों, तो बाएँ आधे वाला पहले जाता है, इसलिए बराबर मान अपना क्रम बनाए रखते हैं। रिकॉर्ड को एक के बाद एक फ़ील्ड से सॉर्ट करते समय स्थिरता मायने रखती है।

इतिहास और उपयोग

John von Neumann ने 1945 में मर्ज सॉर्ट का वर्णन किया, जिससे यह स्टोर्ड-प्रोग्राम कंप्यूटर के लिए लिखे गए शुरुआती एल्गोरिदम में से एक है। क्योंकि यह डेटा को लंबे सिलसिलों में पढ़ता और लिखता है, यह टेप पर डेटा सॉर्ट करने का मानक तरीका था और आज भी मेमोरी में न समाने वाली बड़ी फ़ाइलों के लिए इस्तेमाल होता है। Python और ऑब्जेक्ट के लिए Java में इस्तेमाल होने वाला Timsort एक मर्ज सॉर्ट है, जो पहले से सॉर्ट हिस्से ढूँढ़ता है और छोटे टुकड़ों के लिए इंसर्शन सॉर्ट का इस्तेमाल करता है।

जॉन वॉन नॉइमान, लॉस अलामोस के बैज चित्र में। उन्होंने 1945 में मर्ज सॉर्ट का वर्णन किया, जो संचित-प्रोग्राम कंप्यूटर के लिए लिखे गए सबसे पहले कलनविधियों में से एक है।
जॉन वॉन नॉइमान, लॉस अलामोस के बैज चित्र में। उन्होंने 1945 में मर्ज सॉर्ट का वर्णन किया, जो संचित-प्रोग्राम कंप्यूटर के लिए लिखे गए सबसे पहले कलनविधियों में से एक है।

ख़ुद देखें

ऐप खोलें और आगे दबाएँ। सूची का छायांकित हिस्सा बाँटा या मर्ज किया जा रहा है, और डैश वाली रेखा बीच का स्थान दिखाती है। मर्ज शुरू होने पर दोनों आधे बफ़र वाली पंक्ति में उतर जाते हैं; दोनों सबसे आगे के मानों की तुलना होती है, और छोटा वापस ऊपर जाता है। काउंटर देखें: एक ही लंबाई की हर सूची के लिए लेखन बराबर होते हैं, और तुलनाएँ सॉर्ट की हुई या उल्टी सूची के लिए सबसे कम और रैंडम सूची के लिए सबसे ज़्यादा होती हैं, पर कभी लगभग n log₂ n से ज़्यादा नहीं।

अक्सर पूछे जाने वाले प्रश्न

मर्ज सॉर्ट की टाइम कॉम्प्लेक्सिटी क्या है?

सबसे अच्छी, औसत और सबसे ख़राब, तीनों स्थितियों में O(n log n)। आम संस्करण को बफ़र के लिए O(n) अतिरिक्त मेमोरी चाहिए।

मर्ज सॉर्ट और क्विकसॉर्ट में क्या अंतर है?

दोनों सूची को बाँटकर हिस्सों को सॉर्ट करते हैं। मर्ज सॉर्ट मानों को देखे बिना बीच से बाँटता है और अपना काम मर्ज करते समय करता है; क्विकसॉर्ट अपना काम बाँटते समय करता है, एक पिवट के आसपास मानों को हिलाकर, और उसे मर्ज की ज़रूरत नहीं होती। क्विकसॉर्ट उसी जगह पर सॉर्ट करता है और व्यवहार में अक्सर तेज़ होता है, पर ख़राब इनपुट पर n² तक धीमा हो सकता है और स्थिर नहीं है। मर्ज सॉर्ट हमेशा n log n और स्थिर होता है।

बॉटम-अप मर्ज सॉर्ट क्या है?

रिकर्शन के बिना एक संस्करण: पहले पास-पास के अकेले मानों को जोड़ों में मर्ज करें, फिर जोड़ों को चार-चार में, और इसी तरह, हर दौर में लंबाई दोगुनी करते हुए। यह यहाँ दिखाए गए टॉप-डाउन संस्करण जितना ही काम करता है।

क्या मर्ज सॉर्ट स्थिर है?

हाँ, बशर्ते बराबरी पर बाएँ आधे का मान पहले लिया जाए, जैसा यह ऐप करता है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

मर्ज सॉर्ट आज़माएँ