मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

मर्ज सॉर्ट का एक उदाहरण. सबसे पहले, सूची को सबसे छोटी इकाई (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

विश्लेषण

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

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

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

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

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

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

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

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

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

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

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

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

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid := ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

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

समानांतर विलय के साथ मर्ज सॉर्ट करें

Main article: मर्ज एल्गोरिदम § समानांतर मर्ज

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

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

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

/**
 * A: Input array
 * B: Output array
 * lo: lower bound
 * hi: upper bound
 * off: offset
 */
algorithm parallelMergesort(A, lo, hi, B, off) is
    len := hi - lo + 1
    if len == 1 then
        B[off] := A[lo]
    else let T[1..len] be a new array
        mid := ⌊(lo + hi) / 2⌋ 
        mid' := mid - lo + 1
        fork parallelMergesort(A, lo, mid, T, 1)
        parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
        join 
        parallelMerge(T, 1, mid', mid' + 1, len, B, off)

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

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

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

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

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

algorithm msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) is
    for i = 1 to p do 
	(l_i, r_i) = (0, |S_i|-1)
	
    while there exists i: l_i < r_i do
	// pick Pivot Element in S_j[l_j], .., S_j[r_j], chose random j uniformly
	v := pickPivot(S, l, r)
	for i = 1 to p do 
	    m_i = binarySearch(v, S_i[l_i, r_i]) // sequentially
	if m_1 + ... + m_p >= k then // m_1+ ... + m_p is the global rank of v
	    r := m  // vector assignment
	else
	    l := m 
	
    return l

यदि डेटा सभी $p$,पर समान रूप से वितरित होता है, तो बाइनरीसर्च विधि का 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}}}$ के लिए रैंक के सभी स्प्लिटर तत्व समययोग्य रूप से ढूंढ़े जा सकें। इन स्प्लिटर तत्वों का उपयोग करके प्रत्येक सूची को $p$ भागों में विभाजित किया जा सकता है, जिसमें कुल चलने का समय भागों, के समान कुल चलने के समय के साथ ${\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)$ होता है।

स्यूडोकोड

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

/**
 * d: Unsorted Array of Elements
 * n: Number of Elements
 * p: Number of Processors
 * return Sorted Array
 */
algorithm parallelMultiwayMergesort(d : Array, n : int, p : int) is
    o := new Array[0, n]                         // the output array
    for i = 1 to p do in parallel                // each processor in parallel
        S_i := d[(i-1) * n/p, i * n/p] 	         // Sequence of length n/p
	sort(S_i)                                // sort locally
        synch
	v_i := msSelect([S_1,...,S_p], i * n/p)          // element with global rank i * n/p
        synch
	(S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // split s_i into subsequences

	o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i)  // merge and assign to output array

    return o

विश्लेषण

प्रथमतः, प्रत्येक प्रोसेसर को सौंपे गए $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)$ होगा, जिसके लिए क्रमशः $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$ आकार के समूहों में विभाजित करता है। सभी प्रोसेसर पहले स्थानीय रूप से सॉर्ट करते हैं। एकल स्तर के बहुदिशा मर्जसॉर्ट के विपरीत, इन सरणियों को फिर से $r$ भागों में विभाजित किया जाता है और उचित प्रोसेसर समूहों को सौंपा जाता है। इन कदमों को संघात्मक रूप से पुनरावृत्त किया जाता है। इससे संचार को कम किया जाता है और विशेष रूप से छोटे संदेशों की समस्याओं से बचा जाता है। असली नेटवर्क की पठनीय संरचना का उपयोग प्रोसेसर समूहों को परिभाषित करने के लिए किया जा सकता है (जैसे 19 इंच का रैक, कंप्यूटर क्लस्टर, ... आदि होता है। )

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

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

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

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

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

संदर्भ

• 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