मर्ज सॉर्ट
लिस्ट को दो आधों में बांटता है, हर आधे को सॉर्ट करता है, फिर दोनों सॉर्टेड आधों को मिलाकर एक सॉर्टेड लिस्ट बनाता है।
- सर्वश्रेष्ठ Ω(n log n)
- औसत Θ(n log n)
- सबसे खराब O(n log n)
- मेमोरी O(n)
- स्टेबल
- अतिरिक्त मेमोरी चाहिए
इनका मतलब क्या है?
- सर्वश्रेष्ठ: जब इनपुट इस एल्गोरिदम के लिए सबसे आसान हो, तब लिस्ट के आकार n के साथ समय कैसे बढ़ता है।
- औसत: n के साथ समय की आम बढ़त। n² में वैल्यू की संख्या दोगुनी होने पर लगभग चार गुना समय लगता है; n log n बहुत धीरे बढ़ता है।
- सबसे खराब: सबसे कठिन इनपुट पर बढ़त। तब काम का, जब रफ़्तार कभी नहीं गिरनी चाहिए।
- मेमोरी: लिस्ट के अलावा कितनी अतिरिक्त मेमोरी चाहिए। 1 यानी कुछ वेरिएबल, n यानी लिस्ट की एक कॉपी।
- स्टेबल: दो बराबर वैल्यू अपना मूल क्रम बनाए रखती हैं। रिकॉर्ड के किसी एक फ़ील्ड से सॉर्ट करते समय यह ज़रूरी है।
- अतिरिक्त मेमोरी नहीं चाहिए: लिस्ट के अंदर ही सॉर्ट करता है, दूसरी लिस्ट के बिना।
- तुलना हो रही है
- खिसक रहा है
- अंतिम जगह पर
प्ले दबाएं: रेखाएँ दिखाती हैं कि सॉर्ट के दौरान लागत कैसे बढ़ती है
प्ले दबाएं या एल्गोरिदम को चरण दर चरण देखें।
स्पेस: चलाएं या रोकें। बाएं और दाएं ऐरो: चरण दर चरण। Home और End: सीधे जाएं।
इसे आज़माएं: कम अलग-अलग वैल्यू वाली लिस्ट चुनें। दो वैल्यू बराबर हों तो पहले बाएं आधे वाली ली जाती है, इसलिए बराबर वैल्यू अपना क्रम बनाए रखती हैं।
यह कैसे काम करता है
लिस्ट को तब तक बांटते रहें जब तक हर टुकड़े में एक ही वैल्यू न बचे, जो अपने आप सॉर्टेड है। फिर टुकड़ों को जोड़ों में वापस मिलाएं: दोनों टुकड़ों की पहली वैल्यू की तुलना करें और छोटी वाली लें, बार-बार। एनिमेशन में ऊपर उठी पंक्ति वह अतिरिक्त मेमोरी है जो मिलाते समय लगती है।
यह कब सही विकल्प है
जब ऐसी रफ़्तार चाहिए जो सबसे बुरी स्थिति में भी अच्छी रहे, और बराबर वैल्यू का आपसी क्रम न बदले। Python और Java दोनों मर्ज सॉर्ट का एक रूप इस्तेमाल करते हैं। इसकी कमी है अतिरिक्त मेमोरी की ज़रूरत।