जब हम externally merge sort एक बड़ी फ़ाइल, हम इसे छोटे से विभाजित करते हैं, उन्हें क्रमबद्ध करते हैं, और फिर उन्हें एक बड़ी क्रमबद्ध फ़ाइल में विलय करते हैं।बहु-मार्ग विलय बनाम 2-तरफा विलय
विलय करते समय, हम या तो कई 2-तरफा विलय पास, या एक बहु-मार्ग विलय कर सकते हैं।
मुझे आश्चर्य है कि कौन सा दृष्टिकोण बेहतर है? और क्यों?
एक बहु-मार्ग विलय आम तौर पर बेहतर होता है। पर विचार करें तीन छोटे फ़ाइलें:
a1
a2
a3
और
b1
b2
b3
और अंत में
c1
c2
c3
आप a और b साथ मर्ज करते हैं, हम (माना)
a1
b1
a2
b2
b3
a3
और
c1
c2
c3
एक अंतिम मर्ज अनुसार क्रमबद्ध सूची बनाते हैं, लेकिन सूचना के इस अंतिम मर्ज में हम a और b आइटम फिर से यात्रा करने के लिए है कैसे होगा। यह फिर से विलय हो रहा है जो दो-तरफा विलय को कैस्केड करने में अपर्याप्त है।
इसके बजाय आप क्या कर सकते हैं एक बहु-मार्ग विलय है। हालांकि, सावधान रहें कि आप इसे कैसे करते हैं। विशेष रूप से, बेवकूफ डबल-लूप से बचें जो प्रत्येक कर्सर को स्कैन करता है यह देखने के लिए कि न्यूनतम मूल्य क्या है। इसके बजाए एक मिनी-हीप का प्रयोग करें। यह जटिलता को वापस O(n log n) पर लाएगा।