मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

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

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

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

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

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

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

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

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

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

Main article: Merge algorithm § Parallel merge

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

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

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

/**
 * 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$ क्रमबद्ध अनुक्रमों को मिला दिया जाता है। यह मर्ज वेरिएंट समानांतर रैंडम-एक्सेस मशीन पर सॉर्टिंग एल्गोरिदम का वर्णन करने के लिए उपयुक्त है।

मूल विचार

चार प्रोसेसरों पर समानांतर मल्टीवे विलय प्रक्रिया $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) है

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$, बाइनरीसर्च पद्धति के पी-फोल्ड निष्पादन का चलने का समय है ${\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)$.

स्यूडोकोड

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

/**
 * 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)$ अनुक्रमिक मर्ज एल्गोरिथम का उपयोग करना | पी-वे मर्ज एल्गोरिथम। इस प्रकार, समग्र चलने का समय इसके द्वारा दिया जाता है

${\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