मर्ज सॉर्ट

कंप्यूटर विज्ञानमें,मर्ज सॉर्ट, जिसको आमतौर पर मर्जसॉर्ट बोला जाता है, एक कुशल, सामान्य प्रयोजन, तुलना-आधारित सॉर्टिंग एल्गोरिथ्म है। अधिकांश कार्यान्वयन एक स्थिर सॉर्ट का उत्पादन करते हैं, जिसका अर्थ है कि समान तत्वों का क्रम इनपुट और आउटपुट में समान है। मर्ज सॉर्ट एकविभाजित और विजेता एल्गोरिथ्महै जिसका आविष्कारजॉन वाॅन न्यूमनने १९४५ में किया था।गोल्डस्टाइन और वॉन न्यूमैन की १९४८ की शुरुआत में एक रिपोर्ट में बॉटम-अप मर्जोर्ट का विस्तृत विवरण और विश्लेषण दिखाई दिया।
वैचारिक रूप से, एक मर्ज सॉर्ट इस प्रकार काम करता है:
उदाहरण के लिए टोप-डाउन मर्ज सॉर्ट एल्गोरिथ्म का कोड सी जैसी प्रोग्रामिंग भाषा में, जो पुन: सूची को सब्लिस्ट में विभाजित करता है (जिनको रन्स बोला गया है इस उदाहरण मे) जब तक सब्लिस्ट मे एक से ज़्यादा तत्त्व है।फिर उन सब्लिस्ट को मर्ज करके क्रमबद्ध सूची प्राप्त करी जाती है।इसे समझने में मदद करने के लिए, हम २ तत्वों के साथ एक सूची पर विचार करते है।तत्वों को B[] में कॉपी किया जाता है, फिर A[] में मर्ज किया जाता है।जब पुनरावृत्ति स्तर के नीचे तक पहुँच जाता है, यदि ४ तत्व हैं, तो एकल तत्व A[] से B[] में मर्ज किया जाता है, और फिर पुनरावृत्ति के अगले उच्च स्तर पर, उन २ तत्व रन को A[] में मिला दिया जाता है। यह पैटर्न प्रत्येक स्तर की पुनरावृत्ति के साथ जारी है।
पूरी सूची को क्रमबद्ध TopDownMergeSort(A, B, length(A)) किया जाता है।
उदाहरण के लिए बौटम-अप मर्ज सॉर्ट एल्गोरिथ्म का कोड सी जैसी प्रोग्रामिंग भाषा में, जो सूची को n सब्लिस्ट (जिनको रन्स बोला गया है इस उदाहरण मे) जिनमे एक तत्त्व है।उन सब्लिस्ट को आईट्रेटिवली मर्ज किया जाता है।
प्राकृतिक मर्ज सॉर्ट बौटम-अप मर्ज सॉर्ट एल्गोरिथ्म के समान है सिवाय इसके कि इनपुट में किसी भी स्वाभाविक रूप से होने वाले रन (सॉर्ट किए गए क्रम) का लाभ उठाया जाता है। दोनों मोनोटोनिक और बिटोनिक (बारी-बारी से ऊपर / नीचे) रन का लाभ उठाया जा सकता है, सूचियों (या समकक्ष टेप या फ़ाइलों) के साथ सुविधाजनक डेटा संरचनाएं (फीफो कतार यालीफो ढेरके रूप में उपयोग की जाती हैं)।बौटम-अप मर्ज सॉर्ट में, शुरुआती रन मानता है कि प्रत्येक रन एक आइटम लंबा है।प्रयोग में, यादृच्छिक इनपुट डेटा में कई छोटे रन होंगे जो क्रमबद्ध होगें।विशिष्ट मामले में, प्राकृतिक मर्ज सॉर्ट की जरुरत ना पड़े क्योंकि कम रन को मर्ज करने की आवश्यकता होगी।सर्वोत्तम मामले में, इनपुट पहले से ही सॉर्ट किया गया है (यानी, एक रन है), इसलिए प्राकृतिक मर्ज सॉर्ट को केवल डेटा में एक पास मारने की आवश्यकता होगी। कई वास्तविक मामलों में, लंबे प्राकृतिक रन लग जाते है, और इस कारण से प्राकृतिक मर्ज सॉर्ट का उपयोग टिम्सॉर्ट के प्रमुख घटक के रूप में किया जाता है। उदाहरण के लिए:
टूर्नामेंट रिप्लेसमेंट चयन प्रकार का उपयोग बाहरी सॉर्टिंग एल्गोरिदम के लिए प्रारंभिक रन इकट्ठा करने के लिए किया जाता है।
nऑब्जेक्ट्स को सॉर्ट करने में, मर्ज सॉर्ट मेंO(nlogn) का औसत और सबसे खराब प्रदर्शन होता है। यदि लंबाईnकी सूची के लिए मर्ज के प्रकार का रनिंग टाइमT(n)है, तो पुनरावर्तनT(n) = 2T(n/2) +nएल्गोरिथम की परिभाषा से अनुसरण करता है (एल्गोरिथ्म को दो सूचियों पर लागू करें जिनकी लम्बाई मूल सूची की आधी हो, और परिणामी दो सूचियों को मिलाने के लिए उठाए गएnचरणों को जोड़ें)।बंद रूप फॉर्म मास्टर प्रमेय से विभाजन और जीत की पुनरावृत्ति के लिए अनुसरण करता है।
सबसे खराब स्थिति में, मर्ज सॉर्ट मे तुलना की संख्या सॉर्टिंग संख्याओं द्वारा दी जाती है। ये संख्या (n⌈lgn⌉ − 2+ 1) के बराबर या उससे छोटी होती है, जो कि (nlgn−n+ 1) और (nlgn+n+ O(lgn)) के बीच है।
बड़ेnऔर बेतरतीब ढंग से ऑर्डर की गई इनपुट सूची के लिए, मर्ज की तरह की अपेक्षित (औसत) तुलनाओं की संख्या α · n सबसे खराब स्थिति की तुलना में कम है, जहांα=−1+∑k=0∞12k+1≈0.2645{\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645}।
सबसे खराब स्थिति में, मर्ज सॉर्ट औसत मामले मेंक्विकसॉर्टकी तुलना में लगभग ३९% कम तुलना करता है। चालों के संदर्भ में, मर्ज सॉर्ट की सबसे खराब स्थिति जटिलता हे (n लॉग एन) - क्विकसॉर्ट के सर्वश्रेष्ठ मामले के रूप में एक ही जटिलता है, और मर्ज सॉर्ट का सबसे अच्छा मामला सबसे खराब मामले के रूप में कई पुनरावृत्तियों के बारे में आधा लेता है।
मर्ज सॉर्ट कुछ प्रकार की सूचियों के लिए क्विकसॉर्ट से अधिक कुशल है यदि छांटे जाने वाले डेटा को केवल कुशलता से क्रमिक रूप से एक्सेस किया जा सकता है, और इस प्रकार लिस्प जैसी भाषाओं में लोकप्रिय है, जहां क्रमिक रूप से एक्सेस की गई डेटा संरचनाएं बहुत आम हैं। क्विकॉर्ट के कुछ (कुशल) कार्यान्वयनों के विपरीत, मर्ज सॉर्ट एक स्थिर सॉर्ट है।
मर्ज सॉर्ट कुछ प्रकार की सूचियों के लिए क्विकसॉर्ट से अधिक कुशल है यदि छांटे जाने वाले डेटा को केवल कुशलता से क्रमिक रूप से एक्सेस किया जा सकता है, और इस प्रकार लिस्प जैसी भाषाओं में लोकप्रिय है, जहां क्रमिक रूप से एक्सेस की गई डेटा संरचनाएं बहुत आम हैं। क्विकॉर्ट के कुछ (कुशल) कार्यान्वयनों के विपरीत, मर्ज सॉर्ट एक स्थिर सॉर्ट है।