मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

An example of merge sort. First, divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally, all the elements are sorted and merged.
Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n\log n)$
Best-case performance	$\Omega (n\log n)$ typical, $\Omega (n)$ natural variant
Average performance	$\Theta (n\log n)$
Worst-case space complexity	$O(n)$ total with $O(n)$ auxiliary, $O(1)$ auxiliary with linked lists

कंप्यूटर विज्ञान में, मर्ज सॉर्ट (आमतौर पर मर्ज सॉर्ट के रूप में भी लिखा जाता है) कुशल, सामान्य-उद्देश्य और तुलना सॉर्ट | तुलना-आधारित सॉर्टिंग एल्गोरिथम है। अधिकांश कार्यान्वयन छँटाई एल्गोरिथ्म # स्थिरता उत्पन्न करते हैं, जिसका अर्थ है कि समान तत्वों का क्रम इनपुट और आउटपुट में समान है। मर्ज सॉर्ट फूट डालो और जीतो एल्गोरिथम है जिसका आविष्कार जॉन वॉन न्यूमैन ने 1945 में किया था। 1948 की शुरुआत में हरमन गोल्डस्टाइन और वॉन न्यूमैन की रिपोर्ट में बॉटम-अप मर्ज सॉर्ट का विस्तृत विवरण और विश्लेषण दिखाई दिया।

एल्गोरिथम

संकल्पनात्मक रूप से, मर्ज सॉर्ट निम्नानुसार कार्य करता है:

1. अवर्गीकृत सूची को n सबलिस्ट में विभाजित करें, प्रत्येक में तत्व होता है ( तत्व की सूची को क्रमबद्ध माना जाता है)।
2. बार-बार नए सॉर्ट किए गए सबलिस्ट बनाने के लिए एल्गोरिथम सबलिस्ट को मर्ज करें जब तक कि केवल सबलिस्ट शेष न हो। यह क्रमबद्ध सूची होगी।

टॉप-डाउन कार्यान्वयन

उदाहरण सी-जैसे कोड टॉप-डाउन मर्ज सॉर्ट एल्गोरिथम के लिए इंडेक्स का उपयोग करते हुए जो सूची को फिर से विभाजित करता है (इस उदाहरण में रन कहा जाता है) जब तक सबलिस्ट का आकार 1 नहीं हो जाता है, तब तक उन सबलिस्ट को सॉर्ट की गई सूची बनाने के लिए मर्ज कर देता है। कॉपी बैक स्टेप को रिकर्सन के प्रत्येक स्तर के साथ मर्ज की दिशा को वैकल्पिक करने से बचा जाता है (प्रारंभिक बार की कॉपी को छोड़कर, जिसे टाला भी जा सकता है)। इसे समझने में सहायता के लिए, दो तत्वों वाली सरणी पर विचार करें। तत्वों को बी [] में कॉपी किया जाता है, फिर वापस ए [] में विलय कर दिया जाता है। यदि चार तत्व हैं, जब रिकर्सन स्तर के नीचे पहुंच जाता है, तो ए [] से चलने वाला एकल तत्व बी [] में विलय कर दिया जाता है, और फिर रिकर्सन के अगले उच्च स्तर पर, दो-तत्व रन ए में विलय कर दिए जाते हैं [ ]। यह प्रतिमान प्रत्यावर्तन के प्रत्येक स्तर के साथ जारी रहता है।

<वाक्यविन्यास लैंग = सी> // ऐरे ए [] में सॉर्ट करने के लिए आइटम हैं; सरणी बी [] कार्य सरणी है। शून्य टॉपडाउन मेर्जसॉर्ट (ए [], बी [], एन) {

   कॉपीएरे (ए, 0, एन, बी); // ए [] से बी [] की  बार प्रति
   टॉपडाउनस्प्लिटमर्ज (बी, 0, एन, ए); // बी [] से ए [] में डेटा सॉर्ट करें

}

// ए [] को 2 रनों में विभाजित करें, दोनों रनों को बी [] में क्रमबद्ध करें, दोनों रनों को बी [] से ए [] में मर्ज करें // iBegin समावेशी है; iEnd अनन्य है (A[iEnd] सेट में नहीं है)। शून्य टॉपडाउनस्प्लिटमर्ज (बी [], आईबिगिन, आईएंड, ए []) {

   if (iEnd - iBegin <= 1) // if run size == 1
       वापस करना; // इसे क्रमबद्ध मानें
   // रन को 1 आइटम से अधिक हिस्सों में विभाजित करें
   iMiddle = (iEnd + iBegin) / 2; // iMiddle = मध्य बिंदु
   // पुनरावर्ती रूप से सरणी ए [] से बी [] में दोनों रनों को क्रमबद्ध करें
   टॉपडाउनस्प्लिटमर्ज (ए, आईबिगिन, आईमिडल, बी); // बाएं रन को सॉर्ट करें
   टॉपडाउनस्प्लिटमर्ज (ए, आईमिडल, आईएंड, बी); // सही रन को सॉर्ट करें
   // परिणामी रन को सरणी B [] से A [] में मर्ज करें
   टॉपडाउन मर्ज (बी, आईबिगिन, आईमिडल, आईएंड, ए);

}

// बायाँ स्रोत आधा A [iBegin:iMiddle-1] है। // दायां स्रोत आधा A[iMiddle:iEnd-1] है। // परिणाम बी है [iBegin:iEnd-1]। शून्य टॉपडाउन मेर्ज (ए [], आईबिगिन, आईमिडल, आईएंड, बी []) {

   i = iBegin, j = iMiddle;

   // जबकि बाएँ या दाएँ भाग में तत्व हैं ...
   for (k = iBegin; k <iEnd; k++) {
       // यदि लेफ्ट रन हेड मौजूद है और <= मौजूदा राइट रन हेड है।
       अगर (i <iMiddle && (j>= iEnd || A[i] <= A[j])) {
           बी [के] = ए [i];
           मैं = मैं + 1;
       } अन्य {
           बी [के] = ए [जे];
           जे = जे + 1;
       }
   }

}

शून्य कॉपीएरे (ए [], आईबीगिन, आईएंड, बी []) {

   for (k = iBegin; k <iEnd; k++)
       बी [के] = ए [के];

} </वाक्यविन्यास हाइलाइट> पूरे ऐरे को सॉर्ट करने के द्वारा पूरा किया जाता है TopDownMergeSort(A, B, length(A)).

नीचे-ऊपर कार्यान्वयन

नीचे-ऊपर मर्ज सॉर्ट एल्गोरिथम के लिए सूचकांकों का उपयोग करते हुए सी-जैसे कोड का उदाहरण, जो सूची को आकार 1 के n सबलिस्ट्स (इस उदाहरण में रन कहा जाता है) की सरणी के रूप में मानता है, और पुनरावृत्त रूप से दो बफ़र्स के बीच उप-सूचियों को आगे और पीछे मर्ज करता है:

<वाक्यविन्यास लैंग = सी> // सरणी ए [] में सॉर्ट करने के लिए आइटम हैं; सरणी बी [] कार्य सरणी है शून्य बॉटमअप मेर्जसॉर्ट (ए [], बी [], एन) {

   // ए में चलने वाला प्रत्येक 1-तत्व पहले से ही क्रमबद्ध है।
   // पूरे सरणी को सॉर्ट किए जाने तक 2, 4, 8, 16... लंबाई के क्रमिक रूप से लंबे समय तक सॉर्ट किए गए रन बनाएं।
   के लिए (चौड़ाई = 1; चौड़ाई <n; चौड़ाई = 2 * चौड़ाई)
   {
       // ऐरे ए लंबाई चौड़ाई के रनों से भरा है।
       के लिए (i = 0; i <n; i = i + 2 * चौड़ाई)
       {
           // दो रन मर्ज करें: A[i:i+चौड़ाई-1] और A[i+चौड़ाई:i+2*चौड़ाई-1] से B[]
           // या A[i:n-1] को B[] में कॉपी करें ( if (i+width >= n) )
           बॉटमअपमर्ज (ए, आई, मिन (आई+चौड़ाई, एन), मिन (आई+2*चौड़ाई, एन), बी);
       }
       // अब वर्क एरे बी लंबाई 2 * चौड़ाई के रन से भरा है।
       // अगले पुनरावृत्ति के लिए सरणी B को सरणी A में कॉपी करें।
       //  अधिक कुशल कार्यान्वयन ए और बी की भूमिकाओं की अदला-बदली करेगा।
       कॉपीएरे (बी, ए, एन);
       // अब सरणी ए लंबाई 2 * चौड़ाई के रन से भरा है।
   }

}

// लेफ्ट रन ए [iLeft: iRight-1] है। // राइट रन ए [आईराइट: आईएंड -1] है। शून्य बॉटमअप मर्ज (ए [], आईलेफ्ट, आईराइट, आईएंड, बी []) {

   i = iLeft, j = iRight;
   // जबकि बाएँ या दाएँ भाग में तत्व हैं ...
   के लिए (के = आईलेफ्ट; के <आईएंड; के ++) {
       // यदि लेफ्ट रन हेड मौजूद है और <= मौजूदा राइट रन हेड है।
       अगर (i <iRight && (j>= iEnd || A[i] <= A[j])) {
           बी [के] = ए [i];
           मैं = मैं + 1;
       } अन्य {
           बी [के] = ए [जे];
           जे = जे + 1;
       }
   }

}

शून्य कॉपीएरे (बी [], ए [], एन) {

   के लिए (i = 0; i <n; i++)
       ए [i] = बी [i];

} </वाक्यविन्यास हाइलाइट>

सूचियों का उपयोग करते हुए टॉप-डाउन कार्यान्वयन

टॉप-डाउन मर्ज सॉर्ट एल्गोरिथम के लिए स्यूडोकोड जो इनपुट सूची को छोटे सबलिस्ट में तब तक विभाजित करता है जब तक कि सबलिस्ट को तुच्छ रूप से सॉर्ट नहीं किया जाता है, और फिर कॉल चेन को वापस करते समय सबलिस्ट को मर्ज कर देता है।

फ़ंक्शन मर्ज_सॉर्ट (सूची एम) है
    // बेस केस। परिभाषा के अनुसार शून्य या  तत्वों की सूची क्रमबद्ध है।
    अगर मीटर की लंबाई ≤ 1 तब
        वापसी एम

    //  रिकर्सिव केस। सबसे पहले, सूची को समान आकार के उप-सूचियों में विभाजित करें
    // सूची के पहले भाग और दूसरे भाग से मिलकर बनता है।
    // यह मानकर चलता है कि सूचियां इंडेक्स 0 से शुरू होती हैं
    var बाएँ: = खाली सूची
    वर दाएँ: = खाली सूची
    प्रत्येक x के लिए इंडेक्स i के साथ m में करें
        अगर मैं <(मीटर की लंबाई)/2 तो
            एक्स को बाईं ओर जोड़ें
        अन्य
            x को दाईं ओर जोड़ें

    // पुनरावर्ती रूप से दोनों उपसूचियों को क्रमबद्ध करें।
    बाएं�:= मर्ज_सॉर्ट (बाएं)
    दाएं: = मर्ज_सॉर्ट (दाएं)

    // फिर अब छांटे गए उप-सूचियों को मर्ज करें।
    रिटर्न मर्ज (बाएं, दाएं)

इस उदाहरण में, merge फ़ंक्शन बाएँ और दाएँ सबलिस्ट को मर्ज करता है।

फ़ंक्शन मर्ज (बाएं, दाएं) है
    var परिणाम: = खाली सूची

    जबकि बायां खाली नहीं है और दायां खाली नहीं है
        अगर पहले (बाएं) ≤ पहले (दाएं) तो
            परिणाम के लिए पहले (बाएं) जोड़ें
            वाम: = आराम (बाएं)
        अन्य
            परिणाम के लिए पहले (दाएं) जोड़ें
            दायां�:= आराम(दाएं)

    //  या तो बाएं या दाएं में तत्व बचे हो सकते हैं; इनका सेवन करो।
    // (निम्नलिखित में से केवल  लूप वास्तव में दर्ज किया जाएगा।)
    जबकि बायां खाली नहीं है
        परिणाम के लिए पहले (बाएं) जोड़ें
        वाम: = आराम (बाएं)
    जबकि दायां खाली नहीं है
        परिणाम के लिए पहले (दाएं) जोड़ें
        दायां�:= आराम(दाएं)
    वापसी परिणाम

सूचियों का उपयोग करके नीचे-ऊपर कार्यान्वयन

बॉटम-अप मर्ज सॉर्ट एल्गोरिथ्म के लिए स्यूडोकोड जो नोड्स के संदर्भों के छोटे निश्चित आकार के सरणी का उपयोग करता है, जहां सरणी [i] या तो आकार 2 की सूची का संदर्भ हैⁱ या नल पॉइंटर। नोड नोड के लिए संदर्भ या सूचक है। मर्ज () फ़ंक्शन टॉप-डाउन मर्ज सूचियों के उदाहरण के समान होगा, यह दो पहले से क्रमबद्ध सूचियों को मर्ज करता है, और खाली सूचियों को संभालता है। इस स्थिति में, मर्ज () अपने इनपुट मापदंडों और रिटर्न वैल्यू के लिए नोड का उपयोग करेगा।

'फ़ंक्शन' मर्ज_सॉर्ट (नोड हेड) 'है'
    // वापसी अगर खाली सूची
    'अगर' सिर = शून्य 'फिर'
        'वापसी' शून्य
    'वर' नोड सरणी [32]; प्रारंभ में सभी शून्य
    'वर' नोड परिणाम
    'var' नोड अगला
    'वार' int मैं
    परिणाम := सिर
    // नोड्स को सरणी में मर्ज करें
    'जबकि' परिणाम ≠ शून्य 'करो'
        अगला := परिणाम.अगला;
        परिणाम.अगला: = शून्य
        'for' (i = 0; (i <32) && (array[i] ≠ nil); i += 1) 'do'
            परिणाम: = विलय (सरणी [i], परिणाम)
            सरणी [मैं]: = शून्य
        // सरणी के पिछले छोर पर न जाएं
        'अगर' मैं = 32 'फिर'
            मैं - = 1
        सरणी [i]: = परिणाम
        परिणाम: = अगला
    // सरणी को एकल सूची में मर्ज करें
    परिणाम := शून्य
    'के लिए' (i = 0; i <32; i + = 1) 'करो'
        परिणाम: = विलय (सरणी [i], परिणाम)
    'वापसी' परिणाम

विश्लेषण

पुनरावर्ती मर्ज सॉर्ट एल्गोरिथम 7 पूर्णांक मानों की सरणी को सॉर्ट करने के लिए उपयोग किया जाता है। मर्ज सॉर्ट (टॉप-डाउन) का अनुकरण करने के लिए मानव द्वारा उठाए जाने वाले ये कदम हैं।

एन ऑब्जेक्ट्स को सॉर्ट करने में, मर्ज सॉर्ट का औसत प्रदर्शन और बिग ओ नोटेशन (एन लॉग एन) का सबसे खराब प्रदर्शन होता है। यदि लंबाई n की सूची के लिए मर्ज सॉर्ट का रनिंग टाइम T(n) है, तो पुनरावृत्ति संबंध T(n) = 2T(n/2) + n एल्गोरिथम की परिभाषा से अनुसरण करता है (एल्गोरिथ्म को दो सूचियों पर लागू करें मूल सूची के आधे आकार का, और परिणामी दो सूचियों को मर्ज करने के लिए उठाए गए n चरणों को जोड़ें)। बंद रूप मास्टर प्रमेय (एल्गोरिदम का विश्लेषण) | फूट डालो और जीत पुनरावृत्ति के लिए मास्टर प्रमेय से आता है।

सबसे खराब स्थिति में मर्ज सॉर्ट द्वारा की गई तुलनाओं की संख्या छँटाई संख्याों द्वारा दी गई है। ये संख्याएँ (n ⌈बाइनरी लघुगणक n⌉ − 2 के बराबर या उससे थोड़ी छोटी हैं^⌈lg n⌉ + 1), जो (n lg n − n + 1) और (n lg n + n + O(lg n)) के बीच है। मर्ज सॉर्ट बेस्ट केस अपने सबसे खराब केस के रूप में लगभग आधे पुनरावृत्तियों को लेता है। बड़े एन और बेतरतीब ढंग से आदेशित इनपुट सूची के लिए, मर्ज सॉर्ट की अपेक्षित (औसत) तुलना की संख्या सबसे खराब स्थिति से कम α·n तक पहुंचती है, जहां $\alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.$ सबसे खराब स्थिति में, मर्ज सॉर्ट अपने औसत मामले में क्विकॉर्ट की तुलना में लगभग 39% कम तुलना का उपयोग करता है, और चाल के संदर्भ में, मर्ज सॉर्ट की सबसे खराब स्थिति जटिलता बड़ी ओ नोटेशन (n log n) है - वही जटिलता जो जल्दी से सुलझाएं के सबसे अच्छे मामले में होती है।

कुछ प्रकार की सूचियों के लिए मर्ज सॉर्ट क्विकॉर्ट से अधिक कुशल है यदि सॉर्ट किए जाने वाले डेटा को केवल अनुक्रमिक रूप से कुशलता से एक्सेस किया जा सकता है, और इस प्रकार लिस्प प्रोग्रामिंग भाषा जैसी भाषाओं में लोकप्रिय है, जहां क्रमिक रूप से एक्सेस की गई डेटा संरचनाएं बहुत आम हैं। क्विकॉर्ट के कुछ (कुशल) कार्यान्वयन के विपरीत, मर्ज सॉर्ट स्थिर प्रकार है।

मर्ज सॉर्ट का सबसे आम कार्यान्वयन जगह में सॉर्ट नहीं करता है; इसलिए, इनपुट के मेमोरी आकार को सॉर्ट किए गए आउटपुट में संग्रहीत करने के लिए आवंटित किया जाना चाहिए (नीचे उन विविधताओं के लिए देखें जिन्हें केवल n/2 अतिरिक्त रिक्त स्थान की आवश्यकता है)।

प्राकृतिक मर्ज सॉर्ट

प्राकृतिक मर्ज सॉर्ट बॉटम-अप मर्ज सॉर्ट के समान है, सिवाय इसके कि इनपुट में अनुक्रम (सॉर्ट किए गए अनुक्रम) के किसी भी स्वाभाविक रूप से होने वाले रन का शोषण किया जाता है। दोनों मोनोटोनिक और बिटोनिक (वैकल्पिक ऊपर/नीचे) रन का शोषण किया जा सकता है, सूचियों (या समकक्ष टेप या फाइलों) के साथ सुविधाजनक डेटा संरचनाएं (कतार (सार डेटा प्रकार) या स्टैक (सार डेटा प्रकार) के रूप में उपयोग की जाती हैं)। बॉटम-अप मर्ज सॉर्ट में, शुरुआती बिंदु मानता है कि प्रत्येक रन आइटम लंबा है। व्यवहार में, यादृच्छिक इनपुट डेटा में कई छोटे रन होंगे जो अभी सॉर्ट किए जाते हैं। विशिष्ट मामले में, प्राकृतिक मर्ज छँटाई को उतने पास की आवश्यकता नहीं हो सकती है क्योंकि मर्ज करने के लिए कम रन होते हैं। सबसे अच्छे मामले में, इनपुट पहले से ही क्रमबद्ध है (यानी, रन है), इसलिए प्राकृतिक मर्ज सॉर्ट को डेटा के माध्यम से केवल पास बनाने की आवश्यकता है। कई व्यावहारिक मामलों में, लंबे प्राकृतिक रन मौजूद होते हैं, और इस कारण से टिमसोर्ट के प्रमुख घटक के रूप में प्राकृतिक मर्ज सॉर्ट का उपयोग किया जाता है। उदाहरण:

प्रारंभ करें: 3 4 2 1 7 5 8 9 0 6
रन चुनें : (3 4)(2)(1 7)(5 8 9)(0 6)
मर्ज : (2 3 4)(1 5 7 8 9)(0 6)
विलय : (1 2 3 4 5 7 8 9)(0 6)
मिलाना : (0 1 2 3 4 5 6 7 8 9)

औपचारिक रूप से, प्राकृतिक मर्ज छँटाई को एम-इष्टतम छँटाई-इष्टतम कहा जाता है, जहाँ ${\mathtt {Runs}}(L)$ में रनों की संख्या है $L$, शून्य से कम।

टूर्नामेंट छँटाई का उपयोग बाहरी छँटाई एल्गोरिदम के लिए प्रारंभिक रन इकट्ठा करने के लिए किया जाता है।

पिंग-पोंग मर्ज सॉर्ट

समय में दो ब्लॉकों को मर्ज करने के बजाय, पिंग-पोंग मर्ज समय में चार ब्लॉकों को मर्ज करता है। चार सॉर्ट किए गए ब्लॉकों को साथ सहायक स्थान में दो सॉर्ट किए गए ब्लॉकों में मिला दिया जाता है, फिर दो सॉर्ट किए गए ब्लॉकों को वापस मुख्य मेमोरी में मर्ज कर दिया जाता है। ऐसा करने से कॉपी ऑपरेशन छूट जाता है और चालों की कुल संख्या आधी हो जाती है। 2014 में विकीसॉर्ट द्वारा चार-पर- बार विलय का प्रारंभिक सार्वजनिक डोमेन कार्यान्वयन किया गया था, उस वर्ष बाद में विधि को धैर्य छँटाई के लिए अनुकूलन के रूप में वर्णित किया गया था और इसे पिंग-पोंग विलय का नाम दिया गया था। Quadsort ने इस मेथड को 2020 में लागू किया और इसे Quad Merge का नाम दिया।

इन-प्लेस मर्ज सॉर्ट

सरणियों पर लागू किए जाने पर मर्ज सॉर्ट का दोष यह है O(n) कार्यशील स्मृति आवश्यकताएँ। मेमोरी को कम करने या मर्ज सॉर्ट को पूरी तरह से इन-प्लेस एल्गोरिदम | इन-प्लेस बनाने के लिए कई तरीके सुझाए गए हैं:

• Kronrod (1969) निरंतर अतिरिक्त स्थान का उपयोग करने वाले मर्ज सॉर्ट के वैकल्पिक संस्करण का सुझाव दिया।
• कटजैनेन एट अल। एल्गोरिथ्म प्रस्तुत करें जिसके लिए निरंतर मात्रा में कार्यशील मेमोरी की आवश्यकता होती है: इनपुट ऐरे के तत्व को रखने के लिए पर्याप्त स्टोरेज स्पेस, और होल्ड करने के लिए अतिरिक्त स्थान O(1) इनपुट ऐरे में पॉइंटर्स। वे हासिल करते हैं O(n log n) छोटे स्थिरांक के साथ समयबद्ध, लेकिन उनका एल्गोरिथ्म स्थिर नहीं है।
• इन-प्लेस मर्ज एल्गोरिथम तैयार करने के लिए कई प्रयास किए गए हैं जिन्हें इन-प्लेस मर्ज सॉर्ट तैयार करने के लिए मानक (टॉप-डाउन या बॉटम-अप) मर्ज सॉर्ट के साथ जोड़ा जा सकता है। इस मामले में, इन-प्लेस की धारणा को लॉगरिदमिक स्टैक स्पेस लेने के लिए आराम दिया जा सकता है, क्योंकि मानक मर्ज सॉर्ट को अपने स्वयं के स्टैक उपयोग के लिए उस स्थान की आवश्यकता होती है। यह गेफर्ट एट अल द्वारा दिखाया गया था। कि इन-प्लेस में स्थिर विलय संभव है O(n log n) स्क्रैच स्पेस की निरंतर मात्रा का उपयोग करते हुए समय, लेकिन उनका एल्गोरिथ्म जटिल है और इसमें उच्च स्थिर कारक हैं: लंबाई की सरणियों का विलय n और m ले जा सकते हैं 5n + 12m + o(m) चलता है। इस उच्च स्थिर कारक और जटिल इन-प्लेस एल्गोरिदम को सरल और समझने में आसान बनाया गया था। बिंग-चाओ हुआंग और माइकल ए. लैंगस्टन अतिरिक्त स्थान की निश्चित मात्रा का उपयोग करके क्रमबद्ध सूची को मर्ज करने के लिए सीधा रैखिक समय एल्गोरिदम व्यावहारिक इन-प्लेस मर्ज प्रस्तुत किया। उन दोनों ने क्रोनरोड और अन्य के काम का इस्तेमाल किया है। यह रैखिक समय और निरंतर अतिरिक्त स्थान में विलीन हो जाता है। एल्गोरिथ्म मानक मर्ज सॉर्ट एल्गोरिदम की तुलना में थोड़ा अधिक औसत समय लेता है, O(n) अस्थायी अतिरिक्त मेमोरी कोशिकाओं का दोहन करने के लिए दो से कम कारक से मुक्त होता है। हालांकि एल्गोरिथ्म व्यावहारिक रूप से बहुत तेज है लेकिन यह कुछ सूचियों के लिए अस्थिर भी है। लेकिन इसी तरह की अवधारणाओं का उपयोग करके वे इस समस्या को हल करने में सक्षम हैं। अन्य इन-प्लेस एल्गोरिदम में सिममर्ज शामिल है, जो लेता है O((n + m) log (n + m)) कुल समय और स्थिर है। इस तरह के एल्गोरिथ्म को मर्ज सॉर्ट में प्लग करने से इसकी जटिलता गैर-रैखिक रूप से बढ़ जाती है, लेकिन फिर भी चतुर्रेखीय समय, O(n (log n)²).
• बाहरी छँटाई के कई अनुप्रयोग मर्ज छँटाई के रूप का उपयोग करते हैं जहाँ इनपुट अधिक संख्या में सबलिस्ट तक विभाजित हो जाता है, आदर्श रूप से संख्या जिसके लिए उन्हें विलय करने से अभी भी वर्तमान में संसाधित पृष्ठ (कंप्यूटर मेमोरी) का सेट मुख्य मेमोरी में फिट हो जाता है।
• आधुनिक स्थिर रैखिक और इन-प्लेस मर्ज वैरिएंट ब्लॉक मर्ज सॉर्ट है जो स्वैप स्पेस के रूप में उपयोग करने के लिए अद्वितीय मानों का खंड बनाता है।
• बाइनरी खोजों और घुमावों का उपयोग करके अंतरिक्ष ओवरहेड को sqrt (n) तक कम किया जा सकता है। यह विधि सी ++ एसटीएल लाइब्रेरी और क्वाडोर्ट द्वारा नियोजित है।
• एकाधिक सूचियों में नकल को कम करने का विकल्प सूचना के नए क्षेत्र को प्रत्येक कुंजी के साथ जोड़ना है (एम में तत्वों को कुंजियाँ कहा जाता है)। इस फ़ील्ड का उपयोग सॉर्ट की गई सूची में कुंजियों और किसी भी संबंधित जानकारी को साथ लिंक करने के लिए किया जाएगा ( कुंजी और उससे संबंधित जानकारी को रिकॉर्ड कहा जाता है)। फिर लिंक मानों को बदलकर सॉर्ट की गई सूचियों का विलय आगे बढ़ता है; किसी भी रिकॉर्ड को स्थानांतरित करने की आवश्यकता नहीं है। फ़ील्ड जिसमें केवल लिंक होता है, आम तौर पर पूरे रिकॉर्ड से छोटा होता है इसलिए कम जगह का भी उपयोग किया जाएगा। यह मानक सॉर्टिंग तकनीक है, जो मर्ज सॉर्ट तक सीमित नहीं है।
• स्पेस ओवरहेड को n/2 तक कम करने का सरल तरीका संयुक्त संरचना के रूप में बाएं और दाएं को बनाए रखना है, केवल m के बाएं हिस्से को अस्थायी स्थान में कॉपी करना है, और मर्ज किए गए आउटपुट को m में रखने के लिए मर्ज रूटीन को निर्देशित करना है। इस संस्करण के साथ मर्ज रूटीन के बाहर अस्थायी स्थान आवंटित करना बेहतर है, ताकि केवल आवंटन की आवश्यकता हो। पहले बताई गई अत्यधिक नकल को भी कम किया गया है, क्योंकि रिटर्न रिजल्ट स्टेटमेंट (उपरोक्त छद्म कोड में फ़ंक्शन मर्ज) से पहले लाइनों की अंतिम जोड़ी अतिश्योक्तिपूर्ण हो जाती है।

टेप ड्राइव के साथ प्रयोग करें

मर्ज सॉर्ट प्रकार के एल्गोरिदम ने बड़े डेटा सेट को शुरुआती कंप्यूटरों पर सॉर्ट करने की अनुमति दी थी, जिनमें आधुनिक मानकों द्वारा छोटी रैंडम एक्सेस मेमोरी थी। रिकॉर्ड चुंबकीय टेप पर संग्रहीत किए गए थे और चुंबकीय टेप ड्राइव के किनारों पर संसाधित किए गए थे, जैसे कि ये IBM 729s।

बाहरी सॉर्टिंग मर्ज सॉर्ट डिस्क भंडारण या टेप ड्राइव ड्राइव का उपयोग करने के लिए व्यावहारिक है जब सॉर्ट किया जाने वाला डेटा प्रारंभिक भंडारण में फ़िट होने के लिए बहुत बड़ा होता है। बाहरी सॉर्टिंग बताती है कि डिस्क ड्राइव के साथ मर्ज सॉर्ट कैसे कार्यान्वित किया जाता है। विशिष्ट टेप ड्राइव प्रकार चार टेप ड्राइव का उपयोग करता है। सभी I/O अनुक्रमिक हैं (प्रत्येक पास के अंत में रिवाइंड को छोड़कर)। केवल दो रिकॉर्ड बफ़र्स और कुछ प्रोग्राम चर के साथ न्यूनतम कार्यान्वयन प्राप्त किया जा सकता है।

ए, बी, सी, डी के रूप में चार टेप ड्राइव का नामकरण, ए पर मूल डेटा के साथ, और केवल दो रिकॉर्ड बफ़र्स का उपयोग करते हुए, एल्गोरिथ्म #नीचे-ऊपर_कार्यान्वयन|नीचे-ऊपर कार्यान्वयन के समान है, बजाय टेप ड्राइव के जोड़े का उपयोग करके स्मृति में सरणियों की। मूल एल्गोरिथ्म को निम्नानुसार वर्णित किया जा सकता है:

1. ए से रिकॉर्ड्स के जोड़े को मर्ज करें; सी और डी को वैकल्पिक रूप से दो-रिकॉर्ड सबलिस्ट लिखना।
2. सी और डी से दो-रिकॉर्ड सब्लिस्ट्स को चार-रिकॉर्ड सब्लिस्ट्स में मर्ज करें; इन्हें A और B में बारी-बारी से लिखते हैं।
3. ए और बी से चार-रिकॉर्ड उप-सूचियों को आठ-रिकॉर्ड उप-सूचियों में मर्ज करें; इन्हें बारी-बारी से सी और डी में लिखना
4. तब तक दोहराएं जब तक आपके पास सभी डेटा वाली सूची न हो, लॉग में सॉर्ट किया गया हो₂(एन) गुजरता है।

बहुत कम रनों से शुरू करने के बजाय, आमतौर पर हाइब्रिड एल्गोरिदम का उपयोग किया जाता है, जहां प्रारंभिक पास स्मृति में कई रिकॉर्ड पढ़ेगा, लंबी दौड़ बनाने के लिए आंतरिक सॉर्ट करेगा, और फिर उन लंबे रनों को आउटपुट सेट पर वितरित करेगा। कदम कई शुरुआती पास से बचा जाता है। उदाहरण के लिए, 1024 रिकॉर्ड्स का आंतरिक सॉर्ट नौ पास बचाएगा। आंतरिक छंटाई अक्सर बड़ी होती है क्योंकि इसका ऐसा लाभ होता है। वास्तव में, ऐसी तकनीकें हैं जो प्रारंभिक रन को उपलब्ध आंतरिक मेमोरी से अधिक लंबा बना सकती हैं। उनमें से एक, नुथ का 'स्नोप्लो' (द्विआधारी ढेर|बाइनरी मिन-हीप पर आधारित), उपयोग की गई मेमोरी के आकार के रूप में दो बार (औसतन) रन बनाता है। कुछ ओवरहेड के साथ, उपरोक्त एल्गोरिथ्म को तीन टेपों का उपयोग करने के लिए संशोधित किया जा सकता है। ओ (एन लॉग एन) चलने का समय दो कतार (सार डेटा प्रकार), या ढेर (सार डेटा प्रकार) और कतार, या तीन ढेर का उपयोग करके भी प्राप्त किया जा सकता है। दूसरी दिशा में, k > दो टेप (और मेमोरी में O(k) आइटम) का उपयोग करके, हम k-way मर्ज एल्गोरिथम|k/2-way का उपयोग करके O(log k) समय में टेप संचालन की संख्या को कम कर सकते हैं। विलय।

अधिक परिष्कृत मर्ज सॉर्ट जो टेप (और डिस्क) ड्राइव के उपयोग को अनुकूलित करता है, वह पॉलीफ़ेज़ मर्ज सॉर्ट है।

मर्ज सॉर्ट का अनुकूलन

यादृच्छिक पूर्णांकों की सरणी पर टाइल मर्ज सॉर्ट लागू किया गया। क्षैतिज अक्ष सरणी अनुक्रमणिका है और लंबवत अक्ष पूर्णांक है।

आधुनिक कंप्यूटरों पर, संदर्भ की स्थानीयता सॉफ्टवेयर अनुकूलन में सर्वोपरि हो सकती है, क्योंकि बहुस्तरीय मेमोरी पदानुक्रम का उपयोग किया जाता है। मर्ज सॉर्ट एल्गोरिथम के कैशे (कंप्यूटिंग)-जागरूक संस्करण, जिनके संचालन को विशेष रूप से मशीन के मेमोरी कैश में और बाहर पृष्ठों के संचलन को कम करने के लिए चुना गया है, प्रस्तावित किया गया है। उदाहरण के लिए, दtiled merge sortएल्गोरिथम आकार S की उपसरणियों तक पहुँचने पर उप-सरणियों का विभाजन बंद कर देता है, जहाँ S CPU के कैश में फिट होने वाले डेटा आइटमों की संख्या है। इनमें से प्रत्येक उप-सरणियों को इन-प्लेस सॉर्टिंग एल्गोरिथम जैसे सम्मिलन सॉर्ट के साथ क्रमबद्ध किया जाता है, मेमोरी स्वैप को हतोत्साहित करने के लिए, और सामान्य मर्ज सॉर्ट को मानक पुनरावर्ती फैशन में पूरा किया जाता है। इस एल्गोरिथ्म ने बेहतर प्रदर्शन का प्रदर्शन किया है उन मशीनों पर जो कैश ऑप्टिमाइज़ेशन से लाभान्वित होती हैं। (LaMarca & Ladner 1997)

समानांतर मर्ज सॉर्ट

डिवाइड-एंड-कॉनकेयर एल्गोरिथम | डिवाइड-एंड-कॉनकेयर पद्धति के उपयोग के कारण मर्ज सॉर्ट अच्छी तरह से समानांतर हो जाता है। वर्षों में एल्गोरिथम के कई अलग-अलग समानांतर संस्करण विकसित किए गए हैं। कुछ समानांतर मर्ज सॉर्ट एल्गोरिदम अनुक्रमिक टॉप-डाउन मर्ज एल्गोरिदम से दृढ़ता से संबंधित हैं, जबकि अन्य के पास अलग सामान्य संरचना है और के-वे मर्ज एल्गोरिथम | के-वे मर्ज विधि का उपयोग करते हैं।

=== समानांतर पुनरावर्तन === के साथ मर्ज करें अनुक्रमिक मर्ज सॉर्ट प्रक्रिया को दो चरणों में विभाजित चरण और मर्ज चरण में वर्णित किया जा सकता है। पहले में कई पुनरावर्ती कॉल होते हैं जो बार-बार ही विभाजन प्रक्रिया को तब तक करते हैं जब तक कि अनुवर्ती छँटाई न हो जाए (जिसमें या कोई तत्व न हो)। सहज ज्ञान युक्त दृष्टिकोण उन पुनरावर्ती कॉलों का समानांतरकरण है। निम्नलिखित स्यूडोकोड फोर्क-जॉइन मॉडल कीवर्ड का उपयोग करके समानांतर पुनरावर्तन के साथ मर्ज सॉर्ट का वर्णन करता है:

// सरणी ए के हाय (अनन्य) के माध्यम से तत्वों को क्रमबद्ध करें।
'एल्गोरिदम' विलय (ए, लो, हाय) 'है'
    'अगर' लो + 1 <हाय 'फिर' // दो या दो से अधिक तत्व।
        मध्य := ⌊(लो + हाय) / 2⌋
        'फोर्क' विलय (ए, लो, मिड)
        मर्जसॉर्ट (ए, मिड, हाय)
        'जोड़ना'
        मर्ज (ए, लो, मिड, हाय)

यह एल्गोरिथ्म अनुक्रमिक संस्करण का तुच्छ संशोधन है और अच्छी तरह से समानांतर नहीं होता है। इसलिए, इसका speedup बहुत प्रभावशाली नहीं है। इसमें समानांतर एल्गोरिदम का विश्लेषण # का अवलोकन है $\Theta (n)$, जो केवल सुधार है $\Theta (\log n)$ अनुक्रमिक संस्करण की तुलना में (एल्गोरिदम का परिचय देखें)। यह मुख्य रूप से अनुक्रमिक विलय विधि के कारण है, क्योंकि यह समांतर निष्पादन की बाधा है।

=== समानांतर मर्जिंग === के साथ मर्ज सॉर्ट करें

Main article: Merge algorithm § Parallel merge

समांतर विलय एल्गोरिदम का उपयोग करके बेहतर समांतरता प्राप्त की जा सकती है। एल्गोरिद्म का परिचय | कॉर्मेन एट अल। बाइनरी वेरिएंट प्रस्तुत करें जो दो सॉर्ट किए गए उप-अनुक्रमों को सॉर्ट किए गए आउटपुट अनुक्रम में मिला देता है।

अनुक्रमों में से में (असमान लंबाई होने पर लंबा), मध्य सूचकांक का तत्व चुना जाता है। अन्य अनुक्रम में इसकी स्थिति इस तरह से निर्धारित की जाती है कि यदि यह तत्व इस स्थिति में डाला जाता है तो यह क्रम क्रमबद्ध रहेगा। इस प्रकार, कोई जानता है कि दोनों अनुक्रमों से कितने अन्य तत्व छोटे हैं और आउटपुट अनुक्रम में चयनित तत्व की स्थिति की गणना की जा सकती है। इस तरह से बनाए गए छोटे और बड़े तत्वों के आंशिक अनुक्रमों के लिए, मर्ज एल्गोरिथम को फिर से समानांतर में तब तक निष्पादित किया जाता है जब तक कि पुनरावर्तन का आधार मामला नहीं हो जाता।

निम्नलिखित स्यूडोकोड समानांतर मर्ज एल्गोरिथम (कॉर्मेन एट अल से अपनाया गया) का उपयोग करके संशोधित समानांतर मर्ज सॉर्ट विधि दिखाता है।

/**
 * ए: इनपुट सरणी
 * बी: आउटपुट सरणी
 * लो: निचली सीमा
 * हाय: ऊपरी सीमा
 * ऑफ: ऑफसेट
 */
एल्गोरिथ्म समानांतर मेर्जेसॉर्ट (ए, लो, हाय, बी, ऑफ) है
    लेन�:= हि - लो + 1
    अगर लेन == 1 तब
 B[off] := A[lo]
    वरना T[1..len]  नई सरणी होने दें
        मध्य�:= ⌊(लो + हाय) / 2⌋
        मध्य'�:= मध्य - लो + 1
        कांटा समानांतर मेर्जेसॉर्ट (ए, लो, मिड, टी, 1)
        पैरेलल मेर्जेसॉर्ट (ए, मिड + 1, हाय, टी, मिड' + 1)
        जोड़ना
        समांतर मर्ज (टी, 1, मिड ', मिड' + 1, लेन, बी, ऑफ)

सबसे खराब केस स्पैन के लिए पुनरावृत्ति संबंध का विश्लेषण करने के लिए, पैरेलल मेर्जेसॉर्ट के रिकर्सिव कॉल को उनके समानांतर निष्पादन के कारण केवल बार शामिल किया जाना चाहिए, प्राप्त करना

$$T_{\infty }^{\text{sort}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+\Theta \left(\log(n)^{2}\right).$$

समांतर विलय प्रक्रिया की जटिलता के बारे में विस्तृत जानकारी के लिए, मर्ज एल्गोरिदम # समांतर विलय देखें।

इस पुनरावृत्ति का हल इसके द्वारा दिया गया है

$$T_{\infty }^{\text{sort}}=\Theta \left(\log(n)^{3}\right).$$

यह समांतर विलय एल्गोरिदम समानता तक पहुंचता है ${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$, जो पिछले एल्गोरिथम की समानता से बहुत अधिक है। इस तरह का प्रकार व्यवहार में अच्छा प्रदर्शन कर सकता है जब तेजी से स्थिर अनुक्रमिक सॉर्ट, जैसे सम्मिलन सॉर्ट, और छोटे सरणियों को मर्ज करने के लिए बेस केस के रूप में तेज अनुक्रमिक मर्ज के साथ जोड़ा जाता है।

समानांतर मल्टीवे मर्ज सॉर्ट

यह मर्ज सॉर्ट एल्गोरिदम को बाइनरी मर्ज विधि तक सीमित करने के लिए मनमाना लगता है, क्योंकि आमतौर पर p > 2 प्रोसेसर उपलब्ध होते हैं। के-वे मर्ज एल्गोरिथम का उपयोग करने के लिए बेहतर तरीका हो सकता है | के-वे मर्ज विधि, बाइनरी मर्ज का सामान्यीकरण, जिसमें $k$ क्रमबद्ध अनुक्रमों को मिला दिया जाता है। यह मर्ज वेरिएंट समानांतर रैंडम-एक्सेस मशीन पर सॉर्टिंग एल्गोरिदम का वर्णन करने के लिए उपयुक्त है।

मूल विचार

चार प्रोसेसरों पर समानांतर मल्टीवे विलय प्रक्रिया $t_{0}$ को $t_{3}$.

के अवर्गीकृत अनुक्रम को देखते हुए $n$ तत्वों, लक्ष्य अनुक्रम को क्रमबद्ध करना है $p$ उपलब्ध प्रोसेसर (कंप्यूटिंग)। इन तत्वों को सभी प्रोसेसरों के बीच समान रूप से वितरित किया जाता है और अनुक्रमिक सॉर्टिंग एल्गोरिदम का उपयोग करके स्थानीय रूप से सॉर्ट किया जाता है। इसलिए, अनुक्रम में क्रमबद्ध अनुक्रम होते हैं $S_{1},...,S_{p}$ लंबाई का ${\textstyle \lceil {\frac {n}{p}}\rceil }$. सरलीकरण के लिए $n$ का गुणक हो $p$, ताकि ${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$ के लिए $i=1,...,p$.

इन अनुक्रमों का उपयोग बहु-अनुक्रम चयन/स्प्लिटर चयन करने के लिए किया जाएगा। के लिए $j=1,...,p$, एल्गोरिदम स्प्लिटर तत्वों को निर्धारित करता है $v_{j}$ वैश्विक रैंक के साथ ${\textstyle k=j{\frac {n}{p}}}$. फिर की इसी स्थिति $v_{1},...,v_{p}$ प्रत्येक क्रम में $S_{i}$ बाइनरी सर्च एल्गोरिथम के साथ निर्धारित किया जाता है और इस प्रकार $S_{i}$ आगे विभाजित हैं $p$ अनुवर्ती $S_{i,1},...,S_{i,p}$ साथ ${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(v_{j})\}}$.

इसके अलावा, के तत्व $S_{1,i},...,S_{p,i}$ प्रोसेसर को सौंपा गया है $i$, का अर्थ रैंक के बीच के सभी तत्व हैं ${\textstyle (i-1){\frac {n}{p}}}$ और रैंक ${\textstyle i{\frac {n}{p}}}$, जो सभी में वितरित हैं $S_{i}$. इस प्रकार, प्रत्येक प्रोसेसर को क्रमबद्ध अनुक्रमों का क्रम प्राप्त होता है। तथ्य यह है कि रैंक $k$ विभाजक तत्वों की $v_{i}$ विश्व स्तर पर चुना गया था, दो महत्वपूर्ण गुण प्रदान करता है: ओर, $k$ चुना गया था ताकि प्रत्येक प्रोसेसर अभी भी काम कर सके ${\textstyle n/p}$ असाइनमेंट के बाद तत्व एल्गोरिथ्म पूरी तरह से लोड संतुलन (कंप्यूटिंग) | लोड-संतुलित है। दूसरी ओर, प्रोसेसर पर सभी तत्व $i$ प्रोसेसर पर सभी तत्वों से कम या बराबर हैं $i+1$. इसलिए, प्रत्येक प्रोसेसर के-वे मर्ज एल्गोरिथम | पी-वे मर्ज को स्थानीय रूप से निष्पादित करता है और इस प्रकार इसके उप-अनुक्रमों से क्रमबद्ध अनुक्रम प्राप्त करता है। दूसरी संपत्ति के कारण, कोई और पी-वे-मर्ज नहीं करना पड़ता है, परिणाम केवल प्रोसेसर संख्या के क्रम में साथ रखे जाते हैं।

बहु-अनुक्रम चयन

अपने सरलतम रूप में, दिया गया $p$ क्रमबद्ध अनुक्रम $S_{1},...,S_{p}$ पर समान रूप से वितरित $p$ प्रोसेसर और रैंक $k$, कार्य तत्व खोजना है $x$ वैश्विक रैंक के साथ $k$ अनुक्रमों के मिलन में। इसलिए, इसका उपयोग प्रत्येक को विभाजित करने के लिए किया जा सकता है $S_{i}$ स्प्लिटर इंडेक्स पर दो भागों में $l_{i}$, जहां निचले हिस्से में केवल ऐसे तत्व होते हैं जो इससे छोटे होते हैं $x$, जबकि तत्वों से बड़ा $x$ ऊपरी भाग में स्थित हैं।

प्रस्तुत अनुक्रमिक एल्गोरिदम प्रत्येक अनुक्रम में विभाजन के सूचकांक लौटाता है, उदा। सूचकांक $l_{i}$ क्रम में $S_{i}$ ऐसा है कि $S_{i}[l_{i}]$ से कम वैश्विक रैंक है $k$ और $\mathrm {rank} \left(S_{i}[l_{i}+1]\right)\geq k$. एल्गोरिद्म msSelect(S : क्रमबद्ध अनुक्रमों की सरणी [S_1,..,S_p], k : int) है

    i = 1 से p करने के लिए
(l_i, r_i) = (0, |S_i|-1)

    जबकि वहाँ मौजूद है i: l_i < r_i do
// एस_जे [एल_जे], .., एस_जे [आर_जे] में धुरी तत्व चुनें, समान रूप से यादृच्छिक जे चुना
वी := पिकपिवोट(एस, एल, आर)
i = 1 से p करने के लिए
m_i = बाइनरीसर्च (v, S_i [l_i, r_i]) // क्रमिक रूप से
अगर m_1 + ... + m_p >= k तब // m_1+ ... + m_p v की वैश्विक रैंक है
r := m // वेक्टर असाइनमेंट
अन्य
ल := म

    वापसी एल

जटिलता विश्लेषण के लिए समानांतर रैंडम-एक्सेस मशीन मॉडल चुना जाता है। यदि डेटा समान रूप से सभी पर वितरित किया जाता है $p$, बाइनरीसर्च पद्धति के पी-फोल्ड निष्पादन का चलने का समय है ${\mathcal {O}}\left(p\log \left(n/p\right)\right)$. अपेक्षित पुनरावर्तन गहराई है ${\mathcal {O}}\left(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log(n))$ जैसा कि सामान्य तुरंत चयन में होता है। इस प्रकार समग्र अपेक्षित चलने का समय है ${\mathcal {O}}\left(p\log(n/p)\log(n)\right)$.

समानांतर मल्टीवे मर्ज सॉर्ट पर लागू, इस एल्गोरिथम को समानांतर में लागू किया जाना है जैसे कि रैंक के सभी विभाजक तत्व ${\textstyle i{\frac {n}{p}}}$ के लिए $i=1,..,p$ साथ-साथ पाये जाते हैं। इन फाड़नेवाला तत्वों का उपयोग तब प्रत्येक अनुक्रम को विभाजित करने के लिए किया जा सकता है $p$ भागों, के समान कुल चलने के समय के साथ ${\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)$.

स्यूडोकोड

नीचे, समानांतर मल्टीवे मर्ज सॉर्ट एल्गोरिथम का पूरा स्यूडोकोड दिया गया है। हम मानते हैं कि बहु-अनुक्रम चयन से पहले और बाद में बाधा तुल्यकालन है जैसे कि प्रत्येक प्रोसेसर विभाजन तत्वों और अनुक्रम विभाजन को ठीक से निर्धारित कर सकता है।

/**
 * डी: तत्वों की अवर्गीकृत सरणी
 * एन: तत्वों की संख्या
 * पी: प्रोसेसर की संख्या
 * सॉर्ट किए गए ऐरे को लौटाएं
 */
एल्गोरिदम समानांतर मल्टीवे मेर्जेसॉर्ट (डी: ऐरे, एन: इंट, पी: इंट) है
    ओ: = नया ऐरे [0, एन] // आउटपुट ऐरे
    for i = 1 to p समानांतर में करें // प्रत्येक प्रोसेसर समानांतर में
 S_i := d[(i-1) * n/p, i * n/p] // लंबाई का क्रम n/p
सॉर्ट (S_i) // स्थानीय रूप से सॉर्ट करें
         समय होनेवाला बनाना
v_iv:= msSelect([S_1,...,S_p], i * n/p) // वैश्विक रैंक i * n/p के साथ तत्व
         समय होनेवाला बनाना
(S_i, 1, ..., S_i, p)i:= अनुक्रम_विभाजन (si, v_1, ..., v_p) // बाद में s_i को विभाजित करें

o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // मर्ज करें और आउटपुट ऐरे को असाइन करें

    वापसी ओ

विश्लेषण

सबसे पहले, प्रत्येक प्रोसेसर असाइन किए गए सॉर्ट करता है $n/p$ जटिलता के साथ छँटाई एल्गोरिथ्म का स्थानीय रूप से उपयोग करने वाले तत्व ${\mathcal {O}}\left(n/p\;\log(n/p)\right)$. उसके बाद, फाड़नेवाला तत्वों की समय पर गणना की जानी चाहिए ${\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)$. अंत में, के प्रत्येक समूह $p$ विभाजन को प्रत्येक प्रोसेसर द्वारा चलने वाले समय के साथ समानांतर में विलय करना पड़ता है ${\mathcal {O}}(\log(p)\;n/p)$ अनुक्रमिक मर्ज एल्गोरिथम का उपयोग करना | पी-वे मर्ज एल्गोरिथम। इस प्रकार, समग्र चलने का समय इसके द्वारा दिया जाता है

${\mathcal {O}}\left({\frac {n}{p}}\log \left({\frac {n}{p}}\right)+p\log \left({\frac {n}{p}}\right)\log(n)+{\frac {n}{p}}\log(p)\right)$.

व्यावहारिक अनुकूलन और अनुप्रयोग

मल्टीवे मर्ज सॉर्ट एल्गोरिथम अपनी उच्च समांतरता क्षमता के माध्यम से बहुत स्केलेबल है, जो कई प्रोसेसरों के उपयोग की अनुमति देता है। यह एल्गोरिथम को बड़ी मात्रा में डेटा सॉर्ट करने के लिए व्यवहार्य उम्मीदवार बनाता है, जैसे कि कंप्यूटर क्लस्टर में संसाधित। इसके अलावा, चूंकि ऐसी प्रणालियों में मेमोरी आमतौर पर सीमित संसाधन नहीं होती है, मर्ज सॉर्ट की अंतरिक्ष जटिलता का नुकसान नगण्य है। हालांकि, ऐसी प्रणालियों में अन्य कारक महत्वपूर्ण हो जाते हैं, जिन्हें समानांतर रैंडम-एक्सेस मशीन पर मॉडलिंग करते समय ध्यान में नहीं रखा जाता है। यहां, निम्नलिखित पहलुओं पर विचार करने की आवश्यकता है: मेमोरी पदानुक्रम, जब डेटा प्रोसेसर कैश में फिट नहीं होता है, या प्रोसेसर के बीच डेटा के आदान-प्रदान का संचार ओवरहेड होता है, जो अड़चन बन सकता है जब डेटा को साझा किए गए माध्यम से एक्सेस नहीं किया जा सकता है। याद।

पीटर सैंडर्स (कंप्यूटर वैज्ञानिक) एट अल। अपने पेपर में मल्टीलेवल मल्टीवे मर्जसॉर्ट के लिए थोक तुल्यकालिक समानांतर एल्गोरिथम प्रस्तुत किया है, जो विभाजित करता है $p$ प्रोसेसर में $r$ आकार के समूह $p'$. सभी प्रोसेसर पहले स्थानीय रूप से सॉर्ट करते हैं। सिंगल लेवल मल्टीवे मर्जसॉर्ट के विपरीत, इन अनुक्रमों को तब विभाजित किया जाता है $r$ भागों और उपयुक्त प्रोसेसर समूहों को सौंपा गया। इन चरणों को उन समूहों में पुनरावर्ती रूप से दोहराया जाता है। यह संचार को कम करता है और विशेष रूप से कई छोटे संदेशों के साथ होने वाली समस्याओं से बचाता है। अंतर्निहित वास्तविक नेटवर्क की पदानुक्रमित संरचना का उपयोग प्रोसेसर समूहों (जैसे 19 इंच का रैक, कंप्यूटर क्लस्टर, ...) को परिभाषित करने के लिए किया जा सकता है।

आगे के संस्करण

मर्ज सॉर्ट पहले सॉर्टिंग एल्गोरिदम में से था जहां ओ (1) मर्ज सुनिश्चित करने के लिए रिचर्ड कोल ने चतुर सबसैंपलिंग एल्गोरिदम का उपयोग करके इष्टतम गति प्राप्त की थी। अन्य परिष्कृत समानांतर छँटाई एल्गोरिदम कम स्थिरांक के साथ समान या बेहतर समय सीमा प्राप्त कर सकते हैं। उदाहरण के लिए, 1991 में डेविड पॉवर्स ने समानांतर क्विकसॉर्ट (और संबंधित आपको कामयाबी मिले) का वर्णन किया था जो ओ (लॉग एन) समय में सीआरसीडब्ल्यू समानांतर रैंडम-एक्सेस मशीन (पीआरएएम) पर एन प्रोसेसर के साथ विभाजन को स्पष्ट रूप से निष्पादित करके संचालित कर सकता है। पॉवर्स आगे दिखाता है कि O((log n) पर बैचर के बिटोनिक सॉर्टर का पाइपलाइन संस्करण²) तितली छँटाई नेटवर्क पर समय वास्तव में PRAM पर उसके O(log n) प्रकार की तुलना में तेज़ है, और वह तुलना, मूलांक और समानांतर छँटाई में छिपे हुए ओवरहेड्स की विस्तृत चर्चा प्रदान करता है।

अन्य प्रकार के एल्गोरिदम के साथ तुलना

हालाँकि ढेर बनाएं और छांटें में मर्ज सॉर्ट के समान समय सीमा होती है, इसके लिए मर्ज सॉर्ट के Θ(n) के बजाय केवल Θ(1) सहायक स्थान की आवश्यकता होती है। विशिष्ट आधुनिक आर्किटेक्चर पर, कुशल क्विकॉर्ट कार्यान्वयन आम तौर पर रैम-आधारित सरणियों को सॉर्ट करने के लिए मर्ज सॉर्ट से बेहतर प्रदर्शन करते हैं। दूसरी ओर, मर्ज सॉर्ट स्थिर प्रकार है और धीमी-से-पहुंच अनुक्रमिक मीडिया को संभालने में अधिक कुशल है। किसी लिंक की गई सूची को सॉर्ट करने के लिए मर्ज सॉर्ट अक्सर सबसे अच्छा विकल्प होता है: इस स्थिति में मर्ज सॉर्ट को इस तरह लागू करना अपेक्षाकृत आसान होता है कि इसके लिए केवल Θ(1) अतिरिक्त स्थान की आवश्यकता होती है, और लिंक की धीमी रैंडम-एक्सेस प्रदर्शन सूची कुछ अन्य एल्गोरिदम (जैसे कि क्विकसॉर्ट) खराब प्रदर्शन करती है, और अन्य (जैसे हीप्सोर्ट) पूरी तरह से असंभव है।

पर्ल 5.8 के अनुसार, मर्ज सॉर्ट इसका डिफ़ॉल्ट सॉर्टिंग एल्गोरिथम है (यह पर्ल के पिछले संस्करणों में क्विकॉर्ट था)। जावा मंच में, Arrays.sort() तरीके इस्तेमाल करते हैं मर्ज सॉर्ट या ट्यून्ड क्विकॉर्ट डेटाटाइप के आधार पर और कार्यान्वयन दक्षता के लिए इंसर्शन सॉर्ट पर स्विच करें जब सात से कम सरणी तत्वों को सॉर्ट किया जा रहा हो। लिनक्स कर्नेल अपनी लिंक्ड सूचियों के लिए मर्ज सॉर्ट का उपयोग करता है। पायथन (प्रोग्रामिंग लैंग्वेज) टिम्सोर्ट का उपयोग करता है, मर्ज सॉर्ट और इंसर्शन सॉर्ट का और ट्यूनेड हाइब्रिड, जो जावा 7 में मानक सॉर्ट एल्गोरिथ्म बन गया है (गैर-आदिम प्रकार के सरणियों के लिए), Android (ऑपरेटिंग सिस्टम) पर, और जीएनयू ऑक्टेव में।

संदर्भ

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
• Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical in-place mergesort". Nordic Journal of Computing. 3 (1): 27–40. CiteSeerX 10.1.1.22.8523. ISSN 1236-6064. Archived from the original on 2011-08-07. Retrieved 2009-04-04.. Also Practical In-Place Mergesort. Also [3]
• Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging". Sorting and Searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0.
• Kronrod, M. A. (1969). "Optimal ordering algorithm without operational field". Soviet Mathematics - Doklady. 10: 744.
• LaMarca, A.; Ladner, R. E. (1997). "The influence of caches on the performance of sorting". Proc. 8th Ann. ACM-SIAM Symp. On Discrete Algorithms (SODA97): 370–379. CiteSeerX 10.1.1.31.1153.
• Skiena, Steven S. (2008). "4.5: Mergesort: Sorting by Divide-and-Conquer". The Algorithm Design Manual (2nd ed.). Springer. pp. 120–125. ISBN 978-1-84800-069-8.
• Sun Microsystems. "Arrays API (Java SE 6)". Retrieved 2007-11-19.
• Oracle Corp. "Arrays (Java SE 10 & JDK 10)". Retrieved 2018-07-23.

बाहरी संबंध

• Animated Sorting Algorithms: Merge Sort at the Wayback Machine (archived 6 March 2015) – graphical demonstration
• Open Data Structures - Section 11.1.1 - Merge Sort, Pat Morin