अनुकूली मर्ज सॉर्ट (ADAPTIVE MERGE SORT)
अनुकूली मर्ज सॉर्ट (Adaptive Merge Sort) वही मर्ज करता है जो मर्ज सॉर्ट करता है। हालांकि, प्रारंभिक सब-लिस्ट का आकार एलिमेंट्स की सूची में क्रम (Ordering) के अस्तित्व पर निर्भर करता है बजाय आकार 1 की सब-लिस्ट होने के। उदाहरण के लिए, चित्र में सूची पर विचार करें।
इसमें 2 सॉर्टेड सब-लिस्ट हैं।
- सब-लिस्ट 1: एलिमेंट्स 16, 15, 14, 13 के साथ।
- सब-लिस्ट 2: एलिमेंट्स 9, 10, 11, 12 के साथ।
सब-लिस्ट 1 सॉर्टेड है लेकिन रिवर्स ऑर्डर में। इस प्रकार, सब-लिस्ट 1 को चित्र में दिखाए अनुसार उलट दिया जाता है।
एक बार सब-लिस्ट मिल जाने पर मर्जिंग प्रक्रिया शुरू होती है। अनुकूली मर्ज सॉर्ट सब-लिस्ट को मर्ज करना शुरू करता है। अनुकूली मर्ज सॉर्ट को केवल एक मर्जिंग चरण की आवश्यकता होगी क्योंकि केवल 2 सब-लिस्ट हैं। मर्जिंग का परिणाम चित्र में दिखाया गया है।
डिज़ाइन विचार (Design Idea)
- आवश्यक या रिवर्स ऑर्डर में पहले से सॉर्टेड सब-लिस्ट ढूंढकर शुरू करें
- यदि रिवर्स ऑर्डर में एलिमेंट्स वाली कोई सब-लिस्ट मौजूद है, तो पहली एलिमेंट को अंतिम से, दूसरी को अंतिम से दूसरी से एक्सचेंज करके सब-लिस्ट को उलट दें और इसी तरह जारी रखें।
- सब-लिस्ट को तब तक मर्ज करते रहें जब तक केवल 1 सब-लिस्ट शेष न रह जाए।
अनुकूली मर्ज सॉर्ट विश्लेषण (Adaptive Merge Sort Analysis)
अनुकूली मर्ज सॉर्ट आकार 1 की सब-लिस्ट से शुरू करने के बजाय, सब-लिस्ट ढूंढता है जो पहले से आवश्यक या रिवर्स ऑर्डर में सॉर्टेड हैं। प्रारंभ में पाई गई सब-लिस्ट का आकार न्यूनतम 2 और अधिकतम m होगा (m एलिमेंट्स की संख्या है)।
हालांकि, यदि सब-लिस्ट में रिवर्स ऑर्डर में एलिमेंट्स हैं, तो यह मर्ज ऑपरेशन शुरू करने से पहले लिस्ट को उलट देता है। लिस्ट को उलटने के लिए (m/2) एक्सचेंज ऑपरेशन की आवश्यकता होती है।
सर्वोत्तम स्थिति (Best Case)
यदि सूची पहले से सॉर्टेड ऑर्डर या रिवर्स ऑर्डर में है, तो अनुकूली मर्ज सॉर्ट में केवल एक लिस्ट होगी और किसी मर्ज ऑपरेशन की आवश्यकता नहीं होगी। हालांकि, यह पता लगाने के लिए कि सूची पहले से सॉर्टेड है, O(m) तुलना ऑपरेशन और (m/2) एक्सचेंज ऑपरेशन की आवश्यकता होगी यदि सूची रिवर्स ऑर्डर में सॉर्टेड है। यह अनुकूली मर्ज सॉर्ट को तब भी अनुकूली बनाता है जब सूची रिवर्स ऑर्डर में सॉर्टेड हो।
इस प्रकार सर्वोत्तम स्थिति के लिए समय जटिलता (Time Complexity) निम्नानुसार गणना की जाती है −
T(m) = (m-1) + (m/2) T(m) = (2m-2+m)/2 T(m) = O(m).
हालांकि, अनुकूली मर्ज सॉर्ट मर्ज सॉर्ट की तुलना में O(m) अतिरिक्त स्थान (Additional Space) लागू करता है।
सबसे खराब स्थिति (Worst Case)
अनुकूली मर्ज सॉर्ट सब-लिस्ट ढूंढता है जो पहले से आवश्यक या रिवर्स ऑर्डर में सॉर्टेड है। हालांकि, सबसे खराब स्थिति में कोई आंशिक या कुल क्रमबद्ध एलिमेंट नहीं होते। इस प्रकार, प्रारंभ में पाई गई सब-लिस्ट आकार 2 की होगी। एक बार सब-लिस्ट मिल जाने पर मर्जिंग प्रक्रिया शुरू होती है।
- आकार 2 की सब-लिस्ट मर्ज करने से आकार 4 की सॉर्टेड सब-लिस्ट प्राप्त होती है।
- आकार 4 की सब-लिस्ट मर्ज करने से आकार 8 की सॉर्टेड सब-लिस्ट प्राप्त होती है।
- मर्जिंग की प्रक्रिया तब तक चलती है जब तक 2ᵏ < m। जहां k k-वां मर्जिंग चरण है।
चूंकि अनुकूली मर्ज सॉर्ट के सबसे खराब स्थिति में मर्जिंग चरण मर्ज सॉर्ट के समान हैं। इस प्रकार, अनुकूली मर्ज सॉर्ट के सबसे खराब स्थिति के लिए समय जटिलता मर्ज सॉर्ट के समान है −
T(m) = O(m log m).
