मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

File:Merge-sort-example-300px.gif मर्ज सॉर्ट का एक उदाहरण. सबसे पहले, सूची को सबसे छोटी इकाई (1 तत्व) में विभाजित करें, फिर दो आसन्न सूचियों को क्रमबद्ध करने और मर्ज करने के लिए प्रत्येक तत्व की तुलना आसन्न सूची से करें। अंत में, सभी तत्वों को क्रमबद्ध और विलय कर दिया जाता है।
Class	सॉर्टिंग एल्गोरिदम
Data structure	ऐरे
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 नहीं हो जाता है, तब तक उन उप-सूची को सॉर्ट की गई सूची बनाने के लिए मर्ज कर देता है। प्रत्यावर्तन के प्रत्येक स्तर के साथ मर्ज की दिशा को वैकल्पिक करके कॉपी बैक चरण से बचा जाता है (प्रारंभिक एक बार की प्रतिलिपि को छोड़कर, इससे भी बचा जा सकता है)। इसे समझने में सहायता के लिए, दो तत्वों वाली सरणी पर विचार करें। तत्वों को B [] में कॉपी किया जाता है, फिर वापस A [] में मर्ज कर दिया जाता है। यदि चार तत्व हैं, जब रिकर्सन स्तर के निचले भाग पर पहुंच जाता है, तो A [] से चलने वाला एकल तत्व B[] में मर्ज कर दिया जाता है, और फिर रिकर्सन के अगले उच्च स्तर पर, उन दो-तत्व रन को A[ में मर्ज कर दिया जाता है। ]. यह पैटर्न प्रत्यावर्तन के प्रत्येक स्तर के साथ जारी रहता है।

// 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

विश्लेषण

File:Merge sort algorithm diagram.svg

पुनरावर्ती मर्ज सॉर्ट एल्गोरिथम 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 और बेतरतीब ढंग से ऑर्डर की गई इनपुट सूची के लिए, मर्ज सॉर्ट की अपेक्षित (औसत) तुलनाओं की संख्या सबसे खराब स्थिति से α·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 में विकीसॉर्ट ने चार-एक-साथ मर्ज का एक पब्लिक डोमेन अंतर्गत अमल में लाया गया था, यह तकनीक बाद में धैर्य सॉर्टिंग के लिए अनुकूलन के रूप में वर्णित किया गया था और इसे पिंग-पोंग मर्ज का नाम दिया गया था। क्वादसोर्ट ने 2020 में इस तकनीक को अमल में लाया और उसे क्वाड मर्ज के नाम से जाना जाता है।

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

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

• क्रोनरोड (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) तक कम किया जा सकता है। यह विधि C ++ STL लाइब्रेरी और क्वाडोर्ट द्वारा नियोजित है।
• एकाधिक सूचियों में नकल को कम करने का विकल्प सूचना के नए क्षेत्र को प्रत्येक कुंजी के साथ जोड़ना है (एम में तत्वों को कुंजियाँ कहा जाता है)। इस फ़ील्ड का उपयोग सॉर्ट की गई सूची में कुंजियों और किसी भी संबंधित जानकारी को साथ लिंक करने के लिए किया जाएगा ( कुंजी और उससे संबंधित जानकारी को रिकॉर्ड कहा जाता है)। फिर लिंक मानों को बदलकर सॉर्ट की गई सूचियों का मर्ज आगे बढ़ता है; किसी भी रिकॉर्ड को स्थानांतरित करने की आवश्यकता नहीं है। फ़ील्ड जिसमें केवल लिंक होता है, आम तौर पर पूरे रिकॉर्ड से छोटा होता है इसलिए कम जगह का भी उपयोग किया जाएगा। यह मानक सॉर्टिंग तकनीक है, जो मर्ज सॉर्ट तक सीमित नहीं है।
• स्पेस ओवरहेड को n/2 तक कम करने का सरल तरीका संयुक्त संरचना के रूप में बाएं और दाएं को बनाए रखना है, केवल m के बाएं हिस्से को अस्थायी स्थान में कॉपी करना है, और मर्ज किए गए आउटपुट को m में रखने के लिए मर्ज रूटीन को निर्देशित करना है। इस संस्करण के साथ मर्ज रूटीन के बाहर अस्थायी स्थान आवंटित करना बेहतर है, ताकि केवल आवंटन की आवश्यकता हो। पहले बताई गई अत्यधिक नकल को भी कम किया गया है, क्योंकि रिटर्न रिजल्ट स्टेटमेंट (उपरोक्त छद्म कोड में फ़ंक्शन मर्ज) से पहले लाइनों की अंतिम जोड़ी अतिश्योक्तिपूर्ण हो जाती है।

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

File:IBM 729 Tape Drives.nasa.jpg

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

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

चार टेप ड्राइव को A, B, C, D के रूप में नामित करके, मूल डेटा को A पर रखकर, केवल दो रिकॉर्ड बफर्स का उपयोग करते हुए, एल्गोरिदम बॉटम-अप कार्यान्वयन के समान होता है, मेमोरी में एरे के स्थान पर टेप ड्राइव के जोड़ों का उपयोग करते हुए। मूल एल्गोरिदम को निम्नप्रकार से वर्णित किया जा सकता है:

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

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

ऊपरी एल्गोरिदम में कुछ ओवरहेड के साथ, तीन टेप्स का उपयोग किया जा सकता है। O (n log n) चलने का समय दो कतारों, या एक स्टैक और एक कतार, या तीन स्टैक्स का उपयोग करके भी प्राप्त किया जा सकता है। दूसरी दिशा में, k > दो टेप्स (और O(k) आइटम मेमोरी में) का उपयोग करके, हम k/2-वे मर्ज का उपयोग करके O(log k) बार में टेप आपरेशन की संख्या को कम कर सकते हैं।

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

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

File:Merge sort animation2.gif

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

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

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

मर्ज सॉर्ट पूर्वानुमान और विज्ञान में बड़े पैमाने पर पैरललीकरण के लिए उत्कृष्ट होता है क्योंकि यह विभाजन-और-विजयी �