- मर्ज हो रहा हिस्सा
- तुलना में
- वापस लिखा गया
- अब तक मर्ज हुआ
मर्ज सॉर्ट
मर्ज सॉर्ट एक डिवाइड एंड कॉन्कर एल्गोरिदम है। यह सूची को आधा करता है, हर आधे को इसी तरह सॉर्ट करता है, और बार-बार छोटा सबसे आगे का मान लेकर दोनों सॉर्ट हुए आधे हिस्सों को मर्ज करता है। आधे हिस्सों को बफ़र वाली पंक्ति में जाते और क्रम से वापस लिखे जाते देखें, किसी भी गति से या एक-एक चरण करके, और तुलनाएँ, लेखन और मर्ज गिनें। सॉर्ट देखने के लिए चलाएँ दबाएँ, या एक-एक चरण करके बढ़ने के लिए आगे और पीछे दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। टाइलें तुलनाएँ, सूची में वापस लेखन और मर्ज गिनती हैं। बार की संख्या और उनका शुरुआती क्रम चुनें, या अपनी संख्याएँ लिखें। बोर्ड चुना हो तो तीर कुंजियाँ एक-एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home व End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- बार की संख्या और उनका शुरुआती क्रम चुनें: रैंडम, लगभग सॉर्ट, उल्टा, या कुछ ही अलग मानों वाला। या अपनी संख्याएँ लिखें।
- चलाएँ दबाएँ, या एक-एक चरण करके बढ़ने के लिए आगे और पीछे का इस्तेमाल करें। सॉर्ट में कहीं भी जाने के लिए चरण स्लाइडर खींचें।
- हर मर्ज देखें: दोनों सॉर्ट हुए आधे नीचे बफ़र में जाते हैं, और छोटा सबसे आगे का मान एक-एक करके वापस ऊपर आता है।
मर्ज सॉर्ट कैसे काम करता है
अकेला मान पहले से सॉर्ट होता है। इससे लंबी सूची को दो आधे हिस्सों में बाँटें और हर आधे को मर्ज सॉर्ट से सॉर्ट करें। फिर उन्हें मर्ज करें: हर आधे का सबसे आगे का मान देखें, छोटे मान को नतीजे में ले जाएँ, और तब तक दोहराएँ जब तक दोनों आधे खाली न हो जाएँ। क्योंकि दोनों आधे सॉर्ट हैं, नतीजा भी सॉर्ट होता है।
हमेशा n log n
बार-बार आधा करने से लगभग log₂ n स्तर बनते हैं, और मर्ज का हर स्तर हर मान को एक बार लिखता है, इसलिए सॉर्ट लगभग n log₂ n लेखन करता है, और तुलनाएँ भी ज़्यादा से ज़्यादा इतनी ही। बबल, सिलेक्शन और इंसर्शन सॉर्ट के उलट, यह n² के साथ नहीं बढ़ता, और सूची के क्रम का असर बहुत कम होता है। इसकी कीमत है सूची जितना लंबा बफ़र। मर्ज सॉर्ट स्थिर भी है, इसीलिए यह Python और Java के सॉर्ट का आधार है।
अक्सर पूछे जाने वाले प्रश्न
मर्ज सॉर्ट कैसे काम करता है?
यह सूची को आधा करता है, हर आधे को मर्ज सॉर्ट से सॉर्ट करता है, और बार-बार दोनों के सबसे आगे के मानों में से छोटा लेकर सॉर्ट हुए आधे हिस्सों को मर्ज करता है। एक मान वाली सूची पहले से सॉर्ट होती है, इसलिए बाँटना वहीं रुक जाता है।
मर्ज सॉर्ट कितनी तुलनाएँ करता है?
n मानों के लिए ज़्यादा से ज़्यादा लगभग n log₂ n − n + 1, और कम से कम n log₂ n का लगभग आधा। 40 मानों के लिए यह ज़्यादा से ज़्यादा 177 है। किसी दिए गए n के लिए सूची में वापस लेखन हमेशा उतना ही होता है: मर्ज के हर स्तर पर हर मान का एक।
मर्ज सॉर्ट को अतिरिक्त मेमोरी क्यों चाहिए?
दो आधे हिस्सों को उसी जगह पर जल्दी मर्ज करना मुश्किल है, इसलिए आम मर्ज सॉर्ट आधे हिस्सों को बफ़र में कॉपी करता है और उन्हें क्रम से वापस लिखता है। बफ़र सूची जितना लंबा होता है, और क्विकसॉर्ट और हीप सॉर्ट की तुलना में यही इसकी मुख्य कमी है।
क्या मर्ज सॉर्ट स्थिर है?
हाँ। जब दोनों सबसे आगे के मान बराबर हों, तो बाएँ आधे वाला पहले जाता है, इसलिए बराबर मान अपना मूल क्रम बनाए रखते हैं।
क्या मेरी संख्याएँ कहीं भेजी जाती हैं?
नहीं। सॉर्ट आपके ब्राउज़र में चलता है, और आपकी पिछली सेटिंग्स इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ