मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

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

// Array A[] has the items to sort; array B[] is a work array.
void TopDownMergeSort(A[], B[], n)
{
    CopyArray(A, 0, n, B);           // one time copy of A[] to B[]
    TopDownSplitMerge(A, 0, n, B);   // sort data from B[] into A[]
}

// Split A[] into 2 runs, sort both runs into B[], merge both runs from B[] to A[]
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
    if (iEnd - iBegin <= 1)                     // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sort the left  run
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sort the right run
    // merge the resulting runs from array B[] into A[]
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

//  Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1   ].
// Result is            B[ iBegin:iEnd-1   ].
void TopDownMerge(B[], iBegin, iMiddle, iEnd, A[])
{
    i = iBegin, j = iMiddle;
 
    // While there are elements in the left or right runs...
    for (k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

void CopyArray(A[], iBegin, iEnd, B[])
{
    for (k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

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

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

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

// array A[] has the items to sort; array B[] is a work array
void BottomUpMergeSort(A[], B[], n)
{
    // Each 1-element run in A is already "sorted".
    // Make successively longer sorted runs of length 2, 4, 8, 16... until the whole array is sorted.
    for (width = 1; width < n; width = 2 * width)
    {
        // Array A is full of runs of length width.
        for (i = 0; i < n; i = i + 2 * width)
        {
            // Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
            // or copy A[i:n-1] to B[] ( if (i+width >= n) )
            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
        // Now work array B is full of runs of length 2*width.
        // Copy array B to array A for the next iteration.
        // A more efficient implementation would swap the roles of A and B.
        CopyArray(B, A, n);
        // Now array A is full of runs of length 2*width.
    }
}

//  Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1  ].
void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    // While there are elements in the left or right runs...
    for (k = iLeft; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;    
        }
    } 
}

void CopyArray(B[], A[], n)
{
    for (i = 0; i < n; i++)
        A[i] = B[i];
}

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

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

function merge_sort(list m) is
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the first half and second half of the list.
    // This assumes lists start at index 0.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i < (length of m)/2 then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

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

function merge(left, right) is
    var result := empty list

    while left is not empty and right is not empty do
        if first(left) ≤ first(right) then
            append first(left) to result
            left := rest(left)
        else
            append first(right) to result
            right := rest(right)

    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    while left is not empty do
        append first(left) to result
        left := rest(left)
    while right is not empty do
        append first(right) to result
        right := rest(right)
    return result

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

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

function merge_sort(node head) is
    // return if empty list
    if head = nil then
        return nil
    var node array[32]; initially all nil
    var node result
    var node next
    var int  i
    result := head
    // merge nodes into array
    while result ≠ nil do
        next := result.next;
        result.next := nil
        for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do
            result := merge(array[i], result)
            array[i] := nil
        // do not go past end of array
        if i = 32 then
            i -= 1
        array[i] := result
        result := next
    // merge array into single list
    result := nil
    for (i = 0; i < 32; i += 1) do
        result := merge(array[i], result)
    return result

विश्लेषण

Error creating thumbnail:

पुनरावर्ती मर्ज सॉर्ट एल्गोरिथम 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 अतिरिक्त रिक्त स्थान की आवश्यकता है)।

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

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

Start       :  3  4  2  1  7  5  8  9  0  6
Select runs : (3  4)(2)(1  7)(5  8  9)(0  6)
Merge       : (2  3  4)(1  5  7  8  9)(0  6)
Merge       : (1  2  3  4  5  7  8  9)(0  6)
Merge       : (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 में रखने के लिए मर्ज रूटीन को निर्देशित करना है। इस संस्करण के साथ मर्ज रूटीन के बाहर अस्थायी स्थान आवंटित करना बेहतर है, ताकि केवल आवंटन की आवश्यकता हो। पहले बताई गई अत्यधिक नकल को भी कम किया गया है, क्योंकि रिटर्न रिजल्ट स्टेटमेंट (उपरोक्त छद्म कोड में फ़ंक्शन मर्ज) से पहले लाइनों की अंतिम जोड़ी अतिश्योक्तिपूर्ण हो जाती है।

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

File:IBM 729 Tape Drives.nasa.jpg

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

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

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

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

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

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

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

File:Merge sort animation2.gif

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

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

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

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