मर्ज़ सॉर्ट: Difference between revisions

मर्ज़ सॉर्ट
	मर्ज सॉर्ट का उदाहरण. सबसे पहले, सूची को सबसे छोटी इकाई (1 तत्व) में विभाजित करें, फिर दो आसन्न सूचियों को क्रमबद्ध करने और मर्ज करने के लिए प्रत्येक तत्व की समानता आसन्न सूची से करें। अंत में, सभी तत्वों को क्रमबद्ध और विलय कर दिया जाता है।
Class	सॉर्टिंग एल्गोरिदम
Data structure	ऐरे
Worst-case performance
Best-case performance	typical, natural variant
Average performance
Worst-case space complexity	total with auxiliary, auxiliary with linked lists

Latest revision as of 10:59, 27 July 2023

कंप्यूटर विज्ञान में, मर्ज सॉर्ट (जिसे सामान्यतः मर्जसॉर्ट के रूप में लिखा जाता है) कुशल, सामान्य-उद्देश्य और समानता-आधारित सॉर्टिंग एल्गोरिथम है। अधिकांश कार्यान्वयन सॉर्ट एल्गोरिथ्म स्थिरता उत्पन्न करते हैं, जिसका अर्थ है कि समान तत्वों का क्रम इनपुट और आउटपुट में ही होता है। मर्ज सॉर्ट डिवाइड-और-कॉन्कर एल्गोरिथम है जिसका आविष्कार जॉन वॉन न्यूमैन ने 1945 में किया था।^[2] बॉटम-अप मर्ज सॉर्ट का विस्तृत विवरण और विश्लेषण गोल्डस्टाइन और वन न्यूमैन की रिपोर्ट में 1948 में प्रकट हुआ था।^[3]

एल्गोरिथम

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

अनक्रमित सूची को n उप-सूचियों में विभाजित करें, प्रत्येक में तत्व हो, ( तत्व की सूची को क्रमबद्ध माना जाता है)।
नई क्रमबद्ध उप-सूचियाँ बनाने के लिए उप-सूचियों को बार-बार मर्ज करें जब तक कि केवल उप-सूचियाँ शेष न रह जाएँ। यह क्रमबद्ध सूची होगी।

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

उदाहरण के लिए C-जैसे कोड जो टॉप-डाउन मर्ज सॉर्ट एल्गोरिथम के लिए सूचकांकों का उपयोग करता है जो सूची को पुनरावर्ती रूप से उप-सूचियों में विभाजित करता है (इस उदाहरण में "रन" कहा जाता है) जब तक उप-सूची का आकार 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))द्वारा पूर्ण किया जाता है।

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

बॉटम -उप मर्ज सॉर्ट एल्गोरिथम के लिए सूचकांकों का उपयोग करने वाला उदाहरण C-जैसा कोड जो सूची को आकार 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 चरणों को जोड़ें)।^[4] बंद रूप मास्टर प्रमेय (एल्गोरिदम का विश्लेषण) फूट डालो और जीत पुनरावृत्ति के लिए मास्टर प्रमेय से आता है।

सबसे बुरी स्थिति में मर्ज सॉर्ट द्वारा की गई समानताओं की संख्या सॉर्टिंग संख्याओं द्वारा दी गई है। ये संख्याएँ (n ⌈lg n⌉ − 2^{⌈lg n⌉} + 1) के समान या उससे थोड़ी छोटी हैं), जो (n lg n − n + 1) और (n lg n + n + O(lg n)) के बीच है।^[5] मर्ज सॉर्ट का सबसे अच्छा स्थिति इसके सबसे बुरी स्थितियों की समानता में अधिकतर आधे पुनरावृत्तियों को लेता है।^[6]

बड़े n और क्रमहीन प्रणाली से ऑर्डर की गई इनपुट सूची के लिए, मर्ज सॉर्ट की अपेक्षित (औसत) समानताओं की संख्या सबसे बुरी स्थिति से α·n कम होती है, जहां $\alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.$

सबसे बुरी स्थिति में, मर्ज सॉर्ट अपने औसत स्थितियों में क्विकॉर्ट की समानता में अधिकतर 39% कम समानता का उपयोग करता है, और चाल के संदर्भ में, मर्ज सॉर्ट की सबसे बुरी स्थिति जटिलता बड़ी ओ नोटेशन (n log n) है - वही जटिलता जो जल्दी से सुलझाएं के सबसे अच्छे स्थितियों में होती है।^[6]

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

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

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

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

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 में विकीसॉर्ट ने चार-एक-साथ मर्ज का पब्लिक डोमेन अंतर्गत अमल में लाया गया था, यह कार्यपद्धति बाद में धैर्य सॉर्टिंग के लिए अनुकूलन के रूप में वर्णित किया गया था और इसे पिंग-पोंग मर्ज का नाम दिया गया था।^[9]^[10] क्वादसोर्ट ने 2020 में इस कार्यपद्धति को अमल में लाया और उसे क्वाड मर्ज के नाम से जाना जाता है।^[11]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// 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)$ का सुधार है (एल्गोरिदम का परिचय देखें)। इसका मुख्य कारण सीक्वेंशियल मर्ज मेथड है, क्योंकि यह पैरलल क्रियान्वयनों का बोटलनेक है।

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

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

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

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

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

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

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

मर्ज सॉर्ट एल्गोरिदम को बाइनरी मर्ज मेथड से सीमित करना एकसंयुक्त प्रोसेसर्स पर काम करने के लिए अनुकूल नहीं हो सकता है, क्योंकि सामान्यतः p > 2 प्रोसेसर्स उपलब्ध होते हैं। उत्तम दृष्टिकोण हो सकता है कि K-वे मर्ज मेथड का उपयोग करें, जो बाइनरी मर्ज का विस्तार है, जहां $k$ किए गए अनुक्रमों को मर्ज किया जाता है। यह मर्ज वेरिएंट समानांतर रैंडम-एक्सेस मशीन पर सॉर्टिंग एल्गोरिदम का वर्णन करने के लिए उपयुक्त है।^[20]^[21]

मूल विचार

चार प्रोसेसरों पर समानांतर मल्टीवे मर्ज प्रक्रिया

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$ .^[22]होता है।

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 इंच का रैक, कंप्यूटर क्लस्टर, ... आदि होता है। ) ^[21]

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

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

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

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

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

↑ Skiena (2008, p. 122)
↑ Knuth (1998, p. 158)
↑ Katajainen, Jyrki; Träff, Jesper Larsson (March 1997). "Algorithms and Complexity". Proceedings of the 3rd Italian Conference on Algorithms and Complexity. Italian Conference on Algorithms and Complexity. Lecture Notes in Computer Science. Vol. 1203. Rome. pp. 217–228. CiteSeerX 10.1.1.86.3154. doi:10.1007/3-540-62592-5_74. ISBN 978-3-540-62592-6.
↑ Cormen et al. (2009, p. 36)
↑ The worst case number given here does not agree with that given in Knuth's Art of Computer Programming, Vol 3. The discrepancy is due to Knuth analyzing a variant implementation of merge sort that is slightly sub-optimal
↑ ^6.0 ^6.1 Jayalakshmi, N. (2007). Data structure using C++. ISBN 978-81-318-0020-1. OCLC 849900742.
↑ Cormen et al. (2009, p. 151)
↑ Powers, David M. W.; McMahon, Graham B. (1983). "A compendium of interesting prolog programs". DCS Technical Report 8313 (Report). Department of Computer Science, University of New South Wales.
↑ "WikiSort. Fast and stable sort algorithm that uses O(1) memory. Public domain". 14 Apr 2014.
↑ Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors (PDF). SIGMOD/PODS.
↑ ^11.0 ^11.1 "Quadsort is a branchless stable adaptive merge sort". 8 Jun 2022.
↑ Katajainen, Pasanen & Teuhola (1996)
↑ Geffert, Viliam; Katajainen, Jyrki; Pasanen, Tomi (2000). "Asymptotically efficient in-place merging". Theoretical Computer Science. 237 (1–2): 159–181. doi:10.1016/S0304-3975(98)00162-5.
↑ Huang, Bing-Chao; Langston, Michael A. (March 1988). "Practical In-Place Merging". Communications of the ACM. 31 (3): 348–352. doi:10.1145/42392.42403. S2CID 4841909.
↑ Kim, Pok-Son; Kutzner, Arne (2004). "Stable Minimum Storage Merging by Symmetric Comparisons". Algorithms – ESA 2004. European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723. CiteSeerX 10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN 978-3-540-23025-0.
↑ "A New Method for Efficient in-Place Merging". 1 Sep 2003.
↑ Ferragina, Paolo (2009–2019), "5. Sorting Atomic Items" (PDF), The magic of Algorithms!, p. 5-4, archived (PDF) from the original on 2021-05-12
↑ ^18.0 ^18.1 Cormen et al. (2009, pp. 797–805)
↑ Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog [1] and GitHub repo C++ implementation [2]
↑ Peter Sanders; Johannes Singler (2008). "Lecture Parallel algorithms" (PDF). Retrieved 2020-05-02.
↑ ^21.0 ^21.1 Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (2015). "Practical Massively Parallel Sorting". Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures: 13–23. doi:10.1145/2755573.2755595. ISBN 9781450335881. S2CID 18249978.
↑ Peter Sanders (2019). "Lecture Parallel algorithms" (PDF). Retrieved 2020-05-02.
↑ Cole, Richard (August 1988). "Parallel merge sort". SIAM J. Comput. 17 (4): 770–785. CiteSeerX 10.1.1.464.7118. doi:10.1137/0217049. S2CID 2416667.
↑ Powers, David M. W. (1991). "Parallelized Quicksort and Radixsort with Optimal Speedup". Proceedings of International Conference on Parallel Computing Technologies, Novosibirsk. Archived from the original on 2007-05-25.
↑ Powers, David M. W. (January 1995). Parallel Unification: Practical Complexity (PDF). Australasian Computer Architecture Workshop Flinders University.
↑ "Sort – Perl 5 version 8.8 documentation". Retrieved 2020-08-23.
↑ coleenp (22 Feb 2019). "src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc". OpenJDK.
↑ linux kernel /lib/list_sort.c
↑ jjb (29 Jul 2009). "Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort". Java Development Kit 7 Hg repo. Archived from the original on 2018-01-26. Retrieved 24 Feb 2011.
↑ "Class: java.util.TimSort<T>". Android JDK Documentation. Archived from the original on January 20, 2015. Retrieved 19 Jan 2015.
↑ "liboctave/util/oct-sort.cc". Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Retrieved 18 Feb 2013. Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.

संदर्भ

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

[1] Skiena (2008, p. 122)

[2] Knuth (1998, p. 158)

[3] Katajainen, Jyrki; Träff, Jesper Larsson (March 1997). "Algorithms and Complexity". Proceedings of the 3rd Italian Conference on Algorithms and Complexity. Italian Conference on Algorithms and Complexity. Lecture Notes in Computer Science. Vol. 1203. Rome. pp. 217–228. CiteSeerX 10.1.1.86.3154. doi:10.1007/3-540-62592-5_74. ISBN 978-3-540-62592-6.

[4] Cormen et al. (2009, p. 36)

[5] The worst case number given here does not agree with that given in Knuth's Art of Computer Programming, Vol 3. The discrepancy is due to Knuth analyzing a variant implementation of merge sort that is slightly sub-optimal

[:1-6] 6.0 ^6.1 Jayalakshmi, N. (2007). Data structure using C++. ISBN 978-81-318-0020-1. OCLC 849900742.

[7] Cormen et al. (2009, p. 151)

[8] Powers, David M. W.; McMahon, Graham B. (1983). "A compendium of interesting prolog programs". DCS Technical Report 8313 (Report). Department of Computer Science, University of New South Wales.

[wikisort-9] "WikiSort. Fast and stable sort algorithm that uses O(1) memory. Public domain". 14 Apr 2014.

[10] Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors (PDF). SIGMOD/PODS.

[quadsort-11] 11.0 ^11.1 "Quadsort is a branchless stable adaptive merge sort". 8 Jun 2022.

[12] Katajainen, Pasanen & Teuhola (1996)

[13] Geffert, Viliam; Katajainen, Jyrki; Pasanen, Tomi (2000). "Asymptotically efficient in-place merging". Theoretical Computer Science. 237 (1–2): 159–181. doi:10.1016/S0304-3975(98)00162-5.

[Research_Contributions-14] Huang, Bing-Chao; Langston, Michael A. (March 1988). "Practical In-Place Merging". Communications of the ACM. 31 (3): 348–352. doi:10.1145/42392.42403. S2CID 4841909.

[15] Kim, Pok-Son; Kutzner, Arne (2004). "Stable Minimum Storage Merging by Symmetric Comparisons". Algorithms – ESA 2004. European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723. CiteSeerX 10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN 978-3-540-23025-0.

[16] "A New Method for Efficient in-Place Merging". 1 Sep 2003.

[17] Ferragina, Paolo (2009–2019), "5. Sorting Atomic Items" (PDF), The magic of Algorithms!, p. 5-4, archived (PDF) from the original on 2021-05-12

[clrs-18] 18.0 ^18.1 Cormen et al. (2009, pp. 797–805)

[19] Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog [1] and GitHub repo C++ implementation [2]

[20] Peter Sanders; Johannes Singler (2008). "Lecture Parallel algorithms" (PDF). Retrieved 2020-05-02.

[:0-21] 21.0 ^21.1 Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (2015). "Practical Massively Parallel Sorting". Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures: 13–23. doi:10.1145/2755573.2755595. ISBN 9781450335881. S2CID 18249978.

[22] Peter Sanders (2019). "Lecture Parallel algorithms" (PDF). Retrieved 2020-05-02.

[23] Cole, Richard (August 1988). "Parallel merge sort". SIAM J. Comput. 17 (4): 770–785. CiteSeerX 10.1.1.464.7118. doi:10.1137/0217049. S2CID 2416667.

[24] Powers, David M. W. (1991). "Parallelized Quicksort and Radixsort with Optimal Speedup". Proceedings of International Conference on Parallel Computing Technologies, Novosibirsk. Archived from the original on 2007-05-25.

[25] Powers, David M. W. (January 1995). Parallel Unification: Practical Complexity (PDF). Australasian Computer Architecture Workshop Flinders University.

[26] "Sort – Perl 5 version 8.8 documentation". Retrieved 2020-08-23.

[27] (22 Feb 2019). "src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc". OpenJDK.

[28] ux kernel /lib/list_sort.c

[29] (29 Jul 2009). "Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort". Java Development Kit 7 Hg repo. Archived from the original on 2018-01-26. Retrieved 24 Feb 2011.

[30] "Class: java.util.TimSort<T>". Android JDK Documentation. Archived from the original on January 20, 2015. Retrieved 19 Jan 2015.

[31] "liboctave/util/oct-sort.cc". Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Retrieved 18 Feb 2013. Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

Anonymous

Search

मर्ज़ सॉर्ट: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:59, 27 July 2023

Contents

एल्गोरिथम

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

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

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

सूचियों का उपयोग करके बॉटम -उप कार्यान्वयन

विश्लेषण

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

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

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

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

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

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

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

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

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

मूल विचार

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

स्यूडोकोड

विश्लेषण

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

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

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

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{Short description|Divide and conquer-based sorting algorithm}}
 {{Infobox Algorithm
-|name={{PAGENAMEBASE}}|class=[[Sorting algorithm]]
+|name={{PAGENAMEBASE}}|class=[[सॉर्टिंग एल्गोरिदम]]
 |image=Merge-sort-example-300px.gif
-|caption=An example of merge sort. First, divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally, all the elements are sorted and merged.
+|caption=मर्ज सॉर्ट का उदाहरण. सबसे पहले, सूची को सबसे छोटी इकाई (1 तत्व) में विभाजित करें, फिर दो आसन्न सूचियों को क्रमबद्ध करने और मर्ज करने के लिए प्रत्येक तत्व की समानता आसन्न सूची से करें। अंत में, सभी तत्वों को क्रमबद्ध और विलय कर दिया जाता है।
-|data=[[Array data structure|Array]]
+|data=[[ऐरे डेटा संरचना|ऐरे]]
 |time=<math>O(n\log n)</math>
 |best-time=<math>\Omega(n\log n)</math> typical,
@@ Line 11: / Line 11: @@
 |space=<math>O(n)</math> total with <math>O(n)</math> auxiliary, <math>O(1)</math> auxiliary with linked lists<ref>{{Harvtxt|Skiena|2008|p=122}}</ref>
 }}
-[[कंप्यूटर विज्ञान]] में, मर्ज सॉर्ट (आमतौर पर मर्ज सॉर्ट के रूप में भी लिखा जाता है)  कुशल, सामान्य-उद्देश्य और तुलना सॉर्ट | तुलना-आधारित सॉर्टिंग एल्गोरिथम है। अधिकांश कार्यान्वयन  [[छँटाई एल्गोरिथ्म]] # स्थिरता उत्पन्न करते हैं, जिसका अर्थ है कि समान तत्वों का क्रम इनपुट और आउटपुट में समान है। मर्ज सॉर्ट  फूट डालो और जीतो एल्गोरिथम है जिसका आविष्कार [[जॉन वॉन न्यूमैन]] ने 1945 में किया था।<ref>{{Harvtxt|Knuth|1998|p=158}}</ref> 1948 की शुरुआत में [[हरमन गोल्डस्टाइन]] और वॉन न्यूमैन की  रिपोर्ट में बॉटम-अप मर्ज सॉर्ट का विस्तृत विवरण और विश्लेषण दिखाई दिया।<ref>{{cite conference |chapter=A meticulous analysis of mergesort programs |date=March 1997 |first1=Jyrki |last1=Katajainen |first2=Jesper Larsson |last2=Träff |title=Algorithms and Complexity |series=Lecture Notes in Computer Science |volume=1203 |conference=Italian Conference on Algorithms and Complexity |location=Rome |book-title=Proceedings of the 3rd Italian Conference on Algorithms and Complexity |pages=217–228 |doi=10.1007/3-540-62592-5_74 |isbn=978-3-540-62592-6 |citeseerx=10.1.1.86.3154 |chapter-url=http://hjemmesider.diku.dk/~jyrki/Paper/CIAC97.pdf}}</ref>
+[[कंप्यूटर विज्ञान]] में, '''मर्ज सॉर्ट''' (जिसे सामान्यतः मर्जसॉर्ट के रूप में लिखा जाता है) कुशल, सामान्य-उद्देश्य और समानता-आधारित सॉर्टिंग एल्गोरिथम है। अधिकांश कार्यान्वयन [[छँटाई एल्गोरिथ्म|सॉर्ट एल्गोरिथ्म]] स्थिरता उत्पन्न करते हैं, जिसका अर्थ है कि समान तत्वों का क्रम इनपुट और आउटपुट में ही होता है। मर्ज सॉर्ट डिवाइड-और-कॉन्कर एल्गोरिथम है जिसका आविष्कार [[जॉन वॉन न्यूमैन]] ने 1945 में किया था।<ref>{{Harvtxt|Knuth|1998|p=158}}</ref> बॉटम-अप मर्ज सॉर्ट का विस्तृत विवरण और [[हरमन गोल्डस्टाइन|विश्लेषण गोल्डस्टाइन]] और वन न्यूमैन की रिपोर्ट में 1948 में प्रकट हुआ था।<ref>{{cite conference |chapter=A meticulous analysis of mergesort programs |date=March 1997 |first1=Jyrki |last1=Katajainen |first2=Jesper Larsson |last2=Träff |title=Algorithms and Complexity |series=Lecture Notes in Computer Science |volume=1203 |conference=Italian Conference on Algorithms and Complexity |location=Rome |book-title=Proceedings of the 3rd Italian Conference on Algorithms and Complexity |pages=217–228 |doi=10.1007/3-540-62592-5_74 |isbn=978-3-540-62592-6 |citeseerx=10.1.1.86.3154 |chapter-url=http://hjemmesider.diku.dk/~jyrki/Paper/CIAC97.pdf}}</ref>
 == एल्गोरिथम ==
-संकल्पनात्मक रूप से, मर्ज सॉर्ट निम्नानुसार कार्य करता है:
+सामान्य रूप से, मर्ज सॉर्ट निम्नलिखित विधि से काम करता है:
-# अवर्गीकृत सूची को n सबलिस्ट में विभाजित करें, प्रत्येक में  तत्व होता है ( तत्व की सूची को क्रमबद्ध माना जाता है)।
+# अनक्रमित सूची को n उप-सूचियों में विभाजित करें, प्रत्येक में तत्व हो, ( तत्व की सूची को क्रमबद्ध माना जाता है)।
-# बार-बार नए सॉर्ट किए गए सबलिस्ट बनाने के लिए एल्गोरिथम सबलिस्ट को मर्ज करें जब तक कि केवल  सबलिस्ट शेष न हो। यह क्रमबद्ध सूची होगी।
+# नई क्रमबद्ध उप-सूचियाँ बनाने के लिए उप-सूचियों को बार-बार मर्ज करें जब तक कि केवल उप-सूचियाँ शेष न रह जाएँ। यह क्रमबद्ध सूची होगी।
 === टॉप-डाउन कार्यान्वयन ===
-उदाहरण सी-जैसे कोड टॉप-डाउन मर्ज सॉर्ट एल्गोरिथम के लिए इंडेक्स का उपयोग करते हुए जो सूची को फिर से विभाजित करता है (इस उदाहरण में रन कहा जाता है) जब तक सबलिस्ट का आकार 1 नहीं हो जाता है, तब तक उन सबलिस्ट को  सॉर्ट की गई सूची बनाने के लिए मर्ज कर देता है। कॉपी बैक स्टेप को रिकर्सन के प्रत्येक स्तर के साथ मर्ज की दिशा को वैकल्पिक करने से बचा जाता है (प्रारंभिक  बार की कॉपी को छोड़कर, जिसे टाला भी जा सकता है)। इसे समझने में सहायता के लिए, दो तत्वों वाली  सरणी पर विचार करें। तत्वों को बी [] में कॉपी किया जाता है, फिर वापस ए [] में विलय कर दिया जाता है। यदि चार तत्व हैं, जब रिकर्सन स्तर के नीचे पहुंच जाता है, तो ए [] से चलने वाला एकल तत्व बी [] में विलय कर दिया जाता है, और फिर रिकर्सन के अगले उच्च स्तर पर, दो-तत्व रन ए में विलय कर दिए जाते हैं [ ]। यह प्रतिमान प्रत्यावर्तन के प्रत्येक स्तर के साथ जारी रहता है।
+उदाहरण के लिए C-जैसे कोड जो टॉप-डाउन मर्ज सॉर्ट एल्गोरिथम के लिए सूचकांकों का उपयोग करता है जो सूची को पुनरावर्ती रूप से उप-सूचियों में विभाजित करता है (इस उदाहरण में "रन" कहा जाता है) जब तक उप-सूची का आकार 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];
+ }
+संपूर्ण सरणी को सॉर्ट करना {{mono|TopDownMergeSort(A, B, length(A))}}द्वारा पूर्ण किया जाता है।
-<वाक्यविन्यास लैंग = सी>
+=== बॉटम -उप कार्यान्वयन ===
-// ऐरे ए [] में सॉर्ट करने के लिए आइटम हैं; सरणी बी []  कार्य सरणी है।
-शून्य टॉपडाउन मेर्जसॉर्ट (ए [], बी [], एन)
-{
-    कॉपीएरे (ए, 0, एन, बी); // ए [] से बी [] की  बार प्रति
-    टॉपडाउनस्प्लिटमर्ज (बी, 0, एन, ए); // बी [] से ए [] में डेटा सॉर्ट करें
-}
-// ए [] को 2 रनों में विभाजित करें, दोनों रनों को बी [] में क्रमबद्ध करें, दोनों रनों को बी [] से ए [] में मर्ज करें
+बॉटम -उप मर्ज सॉर्ट एल्गोरिथम के लिए सूचकांकों का उपयोग करने वाला उदाहरण C-जैसा कोड जो सूची को आकार 1 के n उप-सूचियों (इस उदाहरण में "रन" कहा जाता है) की  सरणी के रूप में मानता है, और पुनरावृत्त रूप से दो बफ़र्स के बीच उप-सूचियों को आगे और पीछे मर्ज करता है:
-// iBegin समावेशी है; iEnd अनन्य है (A[iEnd] सेट में नहीं है)।
+ // array A[] has the items to sort; array B[] is a work array
-शून्य टॉपडाउनस्प्लिटमर्ज (बी [], आईबिगिन, आईएंड, ए [])
+ void BottomUpMergeSort(A[], B[], n)
-{
+ {
-    if (iEnd - iBegin <= 1) // if run size == 1
+     // 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.
-    // रन को 1 आइटम से अधिक हिस्सों में विभाजित करें
+     for (width = 1; width < n; width = 2 * width)
-    iMiddle = (iEnd + iBegin) / 2; // iMiddle = मध्य बिंदु
+     {
-    // पुनरावर्ती रूप से सरणी ए [] से बी [] में दोनों रनों को क्रमबद्ध करें
+         // Array A is full of runs of length width.
-    टॉपडाउनस्प्लिटमर्ज (ए, आईबिगिन, आईमिडल, बी); // बाएं रन को सॉर्ट करें
+         for (i = 0; i < n; i = i + 2 * width)
-    टॉपडाउनस्प्लिटमर्ज (ए, आईमिडल, आईएंड, बी); // सही रन को सॉर्ट करें
+         {
-    // परिणामी रन को सरणी B [] से A [] में मर्ज करें
+             // 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);
+         }
-// बायाँ स्रोत आधा A [iBegin:iMiddle-1] है।
+         // Now work array B is full of runs of length 2*width.
-// दायां स्रोत आधा A[iMiddle:iEnd-1] है।
+         // Copy array B to array A for the next iteration.
-// परिणाम बी है [iBegin:iEnd-1]।
+         // 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.
-    i = iBegin, j = iMiddle;
+     }
+ }
+ //  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 (k = iBegin; k <iEnd; k++) {
+  {
-        // यदि लेफ्ट रन हेड मौजूद है और <= मौजूदा राइट रन हेड है।
+     for (i = 0; i < n; i++)
-        अगर (i <iMiddle && (j>= iEnd || A[i] <= A[j])) {
+         A[i] = B[i];
-            बी [के] = ए [i];
+  }
-            मैं = मैं + 1;
-        } अन्य {
-            बी [के] = ए [जे];
-            जे = जे + 1;
-        }
-    }
-}
-शून्य कॉपीएरे (ए [], आईबीगिन, आईएंड, बी [])
-{
-    for (k = iBegin; k <iEnd; k++)
-        बी [के] = ए [के];
-}
-</वाक्यविन्यास हाइलाइट>
-पूरे ऐरे को सॉर्ट करने के द्वारा पूरा किया जाता है {{mono|TopDownMergeSort(A, B, length(A))}}.
-=== नीचे-ऊपर कार्यान्वयन ===
-नीचे-ऊपर मर्ज सॉर्ट एल्गोरिथम के लिए सूचकांकों का उपयोग करते हुए सी-जैसे कोड का उदाहरण, जो सूची को आकार 1 के n सबलिस्ट्स (इस उदाहरण में रन कहा जाता है) की  सरणी के रूप में मानता है, और पुनरावृत्त रूप से दो बफ़र्स के बीच उप-सूचियों को आगे और पीछे मर्ज करता है:
-<वाक्यविन्यास लैंग = सी>
-// सरणी ए [] में सॉर्ट करने के लिए आइटम हैं; सरणी बी []  कार्य सरणी है
-शून्य बॉटमअप मेर्जसॉर्ट (ए [], बी [], एन)
-{
-    // ए में चलने वाला प्रत्येक 1-तत्व पहले से ही क्रमबद्ध है।
-    // पूरे सरणी को सॉर्ट किए जाने तक 2, 4, 8, 16... लंबाई के क्रमिक रूप से लंबे समय तक सॉर्ट किए गए रन बनाएं।
-    के लिए (चौड़ाई = 1; चौड़ाई <n; चौड़ाई = 2 * चौड़ाई)
-    {
-        // ऐरे ए लंबाई चौड़ाई के रनों से भरा है।
-        के लिए (i = 0; i <n; i = i + 2 * चौड़ाई)
-        {
-            // दो रन मर्ज करें: A[i:i+चौड़ाई-1] और A[i+चौड़ाई:i+2*चौड़ाई-1] से B[]
-            // या A[i:n-1] को B[] में कॉपी करें ( if (i+width >= n) )
-            बॉटमअपमर्ज (ए, आई, मिन (आई+चौड़ाई, एन), मिन (आई+2*चौड़ाई, एन), बी);
-        }
-        // अब वर्क एरे बी लंबाई 2 * चौड़ाई के रन से भरा है।
-        // अगले पुनरावृत्ति के लिए सरणी B को सरणी A में कॉपी करें।
-        //  अधिक कुशल कार्यान्वयन ए और बी की भूमिकाओं की अदला-बदली करेगा।
-        कॉपीएरे (बी, ए, एन);
-        // अब सरणी ए लंबाई 2 * चौड़ाई के रन से भरा है।
-    }
-}
-// लेफ्ट रन ए [iLeft: iRight-1] है।
-// राइट रन ए [आईराइट: आईएंड -1] है।
-शून्य बॉटमअप मर्ज (ए [], आईलेफ्ट, आईराइट, आईएंड, बी [])
-{
-    i = iLeft, j = iRight;
-    // जबकि बाएँ या दाएँ भाग में तत्व हैं ...
-    के लिए (के = आईलेफ्ट; के <आईएंड; के ++) {
-        // यदि लेफ्ट रन हेड मौजूद है और <= मौजूदा राइट रन हेड है।
-        अगर (i <iRight && (j>= iEnd || A[i] <= A[j])) {
-            बी [के] = ए [i];
-            मैं = मैं + 1;
-        } अन्य {
-            बी [के] = ए [जे];
-            जे = जे + 1;
-        }
-    }
-}
-शून्य कॉपीएरे (बी [], ए [], एन)
-{
-    के लिए (i = 0; i <n; i++)
-        ए [i] = बी [i];
-}
-</वाक्यविन्यास हाइलाइट>
 === सूचियों का उपयोग करते हुए टॉप-डाउन कार्यान्वयन ===
-टॉप-डाउन मर्ज सॉर्ट एल्गोरिथम के लिए [[स्यूडोकोड]] जो इनपुट सूची को छोटे सबलिस्ट में तब तक विभाजित करता है जब तक कि सबलिस्ट को तुच्छ रूप से सॉर्ट नहीं किया जाता है, और फिर कॉल चेन को वापस करते समय सबलिस्ट को मर्ज कर देता है।
+टॉप-डाउन मर्ज सॉर्ट एल्गोरिथम के लिए [[स्यूडोकोड]] जो इनपुट सूची को पुनरावर्ती रूप से छोटी उपसूचियों में विभाजित करता है जब तक कि उपसूचियां तुच्छ रूप से क्रमबद्ध नहीं हो जाती हैं, और फिर कॉल श्रृंखला को वापस करते समय उपसूचियों को मर्ज कर देता है।
+  '''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'''
-      अगर मीटर की लंबाई ≤ 1 तब
+          '''return''' m
-          वापसी एम
-      // '' रिकर्सिव केस। सबसे पहले, सूची को समान आकार के उप-सूचियों में विभाजित करें''
+      // ''Recursive case. First, divide the list into equal-sized sublists''
-      // ''सूची के पहले भाग और दूसरे भाग से मिलकर बनता है।''
+      // ''consisting of the first half and second half of the list.''
-      // ''यह मानकर चलता है कि सूचियां इंडेक्स 0 से शुरू होती हैं''
+      // ''This assumes lists start at index 0.''
-      var बाएँ: = खाली सूची
+      '''var''' left := empty list
-      वर दाएँ: = खाली सूची
+      '''var''' right := empty list
-      प्रत्येक x के लिए इंडेक्स i के साथ m में करें
+      '''for each''' x '''with index''' i '''in''' m '''do'''
-          अगर मैं <(मीटर की लंबाई)/2 तो
+          '''if''' i < (length of m)/2 '''then'''
-              एक्स को बाईं ओर जोड़ें
+              add x to left
-          अन्य
+          '''else'''
-              x को दाईं ओर जोड़ें
+              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)
+इस उदाहरण में, {{mono|merge}} फ़ंक्शन बाएँ और दाएँ उप-सूची को मर्ज करता है।
-इस उदाहरण में, {{mono|merge}} फ़ंक्शन बाएँ और दाएँ सबलिस्ट को मर्ज करता है।
+  '''function''' merge(left, right) '''is'''
+      '''var''' result := empty list
-  फ़ंक्शन मर्ज (बाएं, दाएं) है
-      var परिणाम: = खाली सूची
-      जबकि बायां खाली नहीं है और दायां खाली नहीं है
+      '''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 की सूची का संदर्भ है<sup>i</sup> या [[नल पॉइंटर]]। नोड  नोड के लिए  संदर्भ या सूचक है। मर्ज () फ़ंक्शन टॉप-डाउन मर्ज सूचियों के उदाहरण के समान होगा, यह दो पहले से क्रमबद्ध सूचियों को मर्ज करता है, और खाली सूचियों को संभालता है। इस स्थिति में, मर्ज () अपने इनपुट मापदंडों और रिटर्न वैल्यू के लिए नोड का उपयोग करेगा।
-  'फ़ंक्शन' मर्ज_सॉर्ट (नोड हेड) 'है'
+=== सूचियों का उपयोग करके बॉटम -उप कार्यान्वयन ===
-      // वापसी अगर खाली सूची
+बॉटम-अप मर्ज सॉर्ट एल्गोरिथ्म के लिए स्यूडोकोड जो नोड्स के संदर्भों के छोटे निश्चित आकार के सरणी का उपयोग करता है, जहां सरणी [i] या तो आकार 2<sup>i</sup> या [[नल पॉइंटर]] की सूची का संदर्भ है। नोड  नोड का संदर्भ या सूचक है। मर्ज () फ़ंक्शन टॉप-डाउन मर्ज सूचियों के उदाहरण के समान होगा, यह पहले से ही क्रमबद्ध सूचियों को मर्ज करता है, और खाली सूचियों को संभालता है। इस स्थिति में, मर्ज () अपने इनपुट पैरामीटर और रिटर्न वैल्यू के लिए नोड का उपयोग करता है।
-      'अगर' सिर = शून्य 'फिर'
+  '''function''' merge_sort(''node'' head) '''is'''
-          'वापसी' शून्य
+      // return if empty list
-      'वर' नोड सरणी [32]; प्रारंभ में सभी शून्य
+      '''if''' head = nil '''then'''
-      'वर' नोड परिणाम
+          '''return''' nil
-      'var' नोड अगला
+      '''var''' ''node'' array[32]; initially all nil
-      'वार' int मैं
+      '''var''' ''node'' result
-      परिणाम := सिर
+      '''var''' ''node'' next
-      // नोड्स को सरणी में मर्ज करें
+      '''var''' ''int''  i
-      'जबकि' परिणाम ≠ शून्य 'करो'
+      result := head
-          अगला := परिणाम.अगला;
+      // merge nodes into array
-          परिणाम.अगला: = शून्य
+      '''while''' result ≠ nil '''do'''
-          'for' (i = 0; (i <32) && (array[i] ≠ nil); i += 1) 'do'
+          next := result.next;
-              परिणाम: = विलय (सरणी [i], परिणाम)
+          result.next := nil
-              सरणी [मैं]: = शून्य
+          '''for''' (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) '''do'''
-          // सरणी के पिछले छोर पर न जाएं
+              result := merge(array[i], result)
-          'अगर' मैं = 32 'फिर'
+              array[i] := nil
-              मैं - = 1
+          // do not go past end of array
-          सरणी [i]: = परिणाम
+          '''if''' i = 32 '''then'''
-          परिणाम: = अगला
+              i -= 1
-      // सरणी को एकल सूची में मर्ज करें
+          array[i] := result
-      परिणाम := शून्य
+          result := next
-      'के लिए' (i = 0; i <32; i + = 1) 'करो'
+      // merge array into single list
-          परिणाम: = विलय (सरणी [i], परिणाम)
+      result := nil
-      'वापसी' परिणाम
+      '''for''' (i = 0; i < 32; i += 1) '''do'''
+          result := merge(array[i], result)
+      '''return''' result
 == विश्लेषण ==
-[[Image:merge sort algorithm diagram.svg|thumb|right|upright=1.35|पुनरावर्ती मर्ज सॉर्ट एल्गोरिथम 7 पूर्णांक मानों की  सरणी को सॉर्ट करने के लिए उपयोग किया जाता है। मर्ज सॉर्ट (टॉप-डाउन) का अनुकरण करने के लिए मानव द्वारा उठाए जाने वाले ये कदम हैं।]]एन ऑब्जेक्ट्स को सॉर्ट करने में, मर्ज सॉर्ट का [[औसत प्रदर्शन]] और [[बिग ओ नोटेशन]] (एन लॉग एन) का [[सबसे खराब प्रदर्शन]] होता है। यदि लंबाई n की सूची के लिए मर्ज सॉर्ट का रनिंग टाइम T(n) है, तो [[पुनरावृत्ति संबंध]] T(n) = 2T(n/2) + n एल्गोरिथम की परिभाषा से अनुसरण करता है (एल्गोरिथ्म को दो सूचियों पर लागू करें मूल सूची के आधे आकार का, और परिणामी दो सूचियों को मर्ज करने के लिए उठाए गए n चरणों को जोड़ें)।<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|p=36}}</ref> बंद रूप [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]] | फूट डालो और जीत पुनरावृत्ति के लिए मास्टर प्रमेय से आता है।
+[[Image:merge sort algorithm diagram.svg|thumb|right|upright=1.35|पुनरावर्ती मर्ज सॉर्ट एल्गोरिथम 7 पूर्णांक मानों की सरणी को सॉर्ट करने के लिए उपयोग किया जाता है। मर्ज सॉर्ट (टॉप-डाउन) का अनुकरण करने के लिए मानव द्वारा उठाए जाने वाले ये कदम हैं।]]इस प्रकार N ऑब्जेक्ट्स को सॉर्ट करने में, मर्ज सॉर्ट का [[औसत प्रदर्शन]] और [[बिग ओ नोटेशन]] (एन लॉग एन) का [[सबसे खराब प्रदर्शन|सबसे बुरी प्रदर्शन]] होता है। यदि लंबाई n की सूची के लिए मर्ज सॉर्ट का रनिंग टाइम T(n) है, तो [[पुनरावृत्ति संबंध]] T(n) = 2T(n/2) + n एल्गोरिथम की परिभाषा का अनुसरण करता है (एल्गोरिथ्म को दो सूचियों पर लागू करें) मूल सूची के आधे आकार का, और परिणामी दो सूचियों को मर्ज करने के लिए उठाए गए n चरणों को जोड़ें)।<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|p=36}}</ref> बंद रूप [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]] फूट डालो और जीत पुनरावृत्ति के लिए मास्टर प्रमेय से आता है।
-सबसे खराब स्थिति में मर्ज सॉर्ट द्वारा की गई तुलनाओं की संख्या [[छँटाई संख्या]]ों द्वारा दी गई है। ये संख्याएँ (n ⌈[[बाइनरी लघुगणक]] n⌉ − 2 के बराबर या उससे थोड़ी छोटी हैं<sup>⌈lg n⌉</sup> + 1), जो (n lg n − n + 1) और (n lg n + n + O(lg n)) के बीच है।<ref>The worst case number given here does not agree with that given in [[Donald Knuth|Knuth]]'s ''[[Art of Computer Programming]], Vol 3''. The discrepancy is due to Knuth analyzing a variant implementation of merge sort that is slightly sub-optimal</ref> मर्ज सॉर्ट बेस्ट केस अपने सबसे खराब केस के रूप में लगभग आधे पुनरावृत्तियों को लेता है।<ref name=":1">{{Cite book|url=https://www.worldcat.org/oclc/849900742|title=Data structure using C++|isbn=978-81-318-0020-1|oclc=849900742|last1=Jayalakshmi|first1=N.|year=2007}}</ref>
+सबसे बुरी स्थिति में मर्ज सॉर्ट द्वारा की गई समानताओं की संख्या [[छँटाई संख्या|सॉर्टिंग संख्याओं]] द्वारा दी गई है। ये संख्याएँ (''n'' ⌈lg ''n''⌉ − 2<sup>⌈lg ''n''⌉</sup> + 1) के समान या उससे थोड़ी छोटी हैं), जो (''n'' lg ''n'' − ''n'' + 1) और (n lg n + n + O(lg n)) के बीच है।<ref>The worst case number given here does not agree with that given in [[Donald Knuth|Knuth]]'s ''[[Art of Computer Programming]], Vol 3''. The discrepancy is due to Knuth analyzing a variant implementation of merge sort that is slightly sub-optimal</ref> मर्ज सॉर्ट का सबसे अच्छा स्थिति इसके सबसे बुरी स्थितियों की समानता में अधिकतर आधे पुनरावृत्तियों को लेता है।<ref name=":1">{{Cite book|url=https://www.worldcat.org/oclc/849900742|title=Data structure using C++|isbn=978-81-318-0020-1|oclc=849900742|last1=Jayalakshmi|first1=N.|year=2007}}</ref>
-बड़े एन और  बेतरतीब ढंग से आदेशित इनपुट सूची के लिए, मर्ज सॉर्ट की अपेक्षित (औसत) तुलना की संख्या सबसे खराब स्थिति से कम α·n तक पहुंचती है, जहां <math>\alpha = -1 + \sum_{k=0}^\infty \frac1{2^k+1} \approx 0.2645.</math>
-सबसे खराब स्थिति में, मर्ज सॉर्ट अपने औसत मामले में क्विकॉर्ट की तुलना में लगभग 39% कम तुलना का उपयोग करता है, और चाल के संदर्भ में, मर्ज सॉर्ट की सबसे खराब स्थिति जटिलता बड़ी ओ नोटेशन (n log n) है - वही जटिलता जो [[जल्दी से सुलझाएं]] के सबसे अच्छे मामले में होती है।<ref name=":1" />
-कुछ प्रकार की सूचियों के लिए मर्ज सॉर्ट क्विकॉर्ट से अधिक कुशल है यदि सॉर्ट किए जाने वाले डेटा को केवल अनुक्रमिक रूप से कुशलता से एक्सेस किया जा सकता है, और इस प्रकार [[लिस्प प्रोग्रामिंग भाषा]] जैसी भाषाओं में लोकप्रिय है, जहां क्रमिक रूप से एक्सेस की गई डेटा संरचनाएं बहुत आम हैं। क्विकॉर्ट के कुछ (कुशल) कार्यान्वयन के विपरीत, मर्ज सॉर्ट  स्थिर प्रकार है।
+बड़े n और क्रमहीन प्रणाली से ऑर्डर की गई इनपुट सूची के लिए, मर्ज सॉर्ट की अपेक्षित (औसत) समानताओं की संख्या सबसे बुरी स्थिति से α·n कम होती है, जहां<math>\alpha = -1 + \sum_{k=0}^\infty \frac1{2^k+1} \approx 0.2645.</math>
-मर्ज सॉर्ट का सबसे आम कार्यान्वयन जगह में सॉर्ट नहीं करता है;<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|p=151}}</ref> इसलिए, इनपुट के मेमोरी आकार को सॉर्ट किए गए आउटपुट में संग्रहीत करने के लिए आवंटित किया जाना चाहिए (नीचे उन विविधताओं के लिए देखें जिन्हें केवल n/2 अतिरिक्त रिक्त स्थान की आवश्यकता है)।
+सबसे बुरी स्थिति में, मर्ज सॉर्ट अपने औसत स्थितियों में क्विकॉर्ट की समानता में अधिकतर 39% कम समानता का उपयोग करता है, और चाल के संदर्भ में, मर्ज सॉर्ट की सबसे बुरी स्थिति जटिलता बड़ी ओ नोटेशन (n log n) है - वही जटिलता जो [[जल्दी से सुलझाएं]] के सबसे अच्छे स्थितियों में होती है।<ref name=":1" />
-== प्राकृतिक मर्ज सॉर्ट ==
+कुछ प्रकार की सूचियों के लिए मर्ज सॉर्ट क्विकॉर्ट से अधिक कुशल है यदि सॉर्ट किए जाने वाले डेटा को केवल अनुक्रमिक रूप से कुशलता से एक्सेस किया जा सकता है, और इस प्रकार [[लिस्प प्रोग्रामिंग भाषा]] जैसी भाषाओं में लोकप्रिय है, जहां क्रमिक रूप से एक्सेस की गई डेटा संरचनाएं बहुत आम हैं। क्विकॉर्ट के कुछ (कुशल) कार्यान्वयन के विपरीत, मर्ज सॉर्ट स्थिर प्रकार है।
-प्राकृतिक मर्ज सॉर्ट बॉटम-अप मर्ज सॉर्ट के समान है, सिवाय इसके कि इनपुट में अनुक्रम (सॉर्ट किए गए अनुक्रम) के किसी भी स्वाभाविक रूप से होने वाले रन का शोषण किया जाता है। दोनों मोनोटोनिक और बिटोनिक (वैकल्पिक ऊपर/नीचे) रन का शोषण किया जा सकता है, सूचियों (या समकक्ष टेप या फाइलों) के साथ सुविधाजनक डेटा संरचनाएं ([[कतार (सार डेटा प्रकार)]] या स्टैक (सार डेटा प्रकार) के रूप में उपयोग की जाती हैं)।<ref>{{cite report |last1=Powers |first1=David M. W. |last2=McMahon |first2=Graham B. |date=1983 |section=A compendium of interesting prolog programs |title=DCS Technical Report 8313 |publisher=Department of Computer Science, University of New South Wales}}</ref> बॉटम-अप मर्ज सॉर्ट में, शुरुआती बिंदु मानता है कि प्रत्येक रन  आइटम लंबा है। व्यवहार में, यादृच्छिक इनपुट डेटा में कई छोटे रन होंगे जो अभी सॉर्ट किए जाते हैं। विशिष्ट मामले में, प्राकृतिक मर्ज छँटाई को उतने पास की आवश्यकता नहीं हो सकती है क्योंकि मर्ज करने के लिए कम रन होते हैं। सबसे अच्छे मामले में, इनपुट पहले से ही क्रमबद्ध है (यानी,  रन है), इसलिए प्राकृतिक मर्ज सॉर्ट को डेटा के माध्यम से केवल  पास बनाने की आवश्यकता है। कई व्यावहारिक मामलों में, लंबे प्राकृतिक रन मौजूद होते हैं, और इस कारण से [[टिमसोर्ट]] के प्रमुख घटक के रूप में प्राकृतिक मर्ज सॉर्ट का उपयोग किया जाता है। उदाहरण:
+मर्ज सॉर्ट का सबसे आम कार्यान्वयन जगह में सॉर्ट नहीं होता है;<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|p=151}}</ref> इसलिए, सॉर्ट किए गए आउटपुट को संग्रहीत करने के लिए इनपुट की मेमोरी आकार को आवंटित किया जाना चाहिए (उन विविधताओं के लिए नीचे देखें जिन्हें केवल n/2 अतिरिक्त रिक्त स्थान की आवश्यकता होती है)।
- प्रारंभ करें: 3 4 2 1 7 5 8 9 0 6
+== प्राकृतिक मर्ज सॉर्ट ==
- रन चुनें : (3 4)(2)(1 7)(5 8 9)(0 6)
- मर्ज : (2 3 4)(1 5 7 8 9)(0 6)
- विलय : (1 2 3 4 5 7 8 9)(0 6)
- मिलाना : (0 1 2 3 4 5 6 7 8 9)
-औपचारिक रूप से, प्राकृतिक मर्ज छँटाई को [[एम-इष्टतम छँटाई]]-इष्टतम कहा जाता है, जहाँ <math>\mathtt{Runs}(L)</math> में रनों की संख्या है <math>L</math>, शून्य से  कम।
+प्राकृतिक मर्ज सॉर्ट बॉटम-अप मर्ज सॉर्ट के समान होता है, अतिरिक्त इसके कि इनपुट में अनुक्रम (सॉर्ट गए क्रमबद्ध अनुक्रम) के किसी भी स्वाभाविक रूप से होने वाले रन का शोषण किया जाता है। दोनों मोनोटोनिक और बिटोनिक (वैकल्पिक ऊपर/नीचे) रन का शोषण किया जा सकता है, सूचियों (या समकक्ष टेप या फाइलों) के साथ सुविधाजनक डेटा संरचनाएं ([[कतार (सार डेटा प्रकार)]] या स्टैक (सार डेटा प्रकार) के रूप में उपयोग की जाती हैं)।<ref>{{cite report |last1=Powers |first1=David M. W. |last2=McMahon |first2=Graham B. |date=1983 |section=A compendium of interesting prolog programs |title=DCS Technical Report 8313 |publisher=Department of Computer Science, University of New South Wales}}</ref> बॉटम-अप मर्ज सॉर्ट में, प्रारंभिक बिंदु मानता है कि प्रत्येक रन आइटम लंबा है। व्यवहार में, यादृच्छिक इनपुट डेटा में कई छोटे रन होंगे जो अभी सॉर्ट किए जाते हैं। विशिष्ट स्थितियों में, प्राकृतिक मर्ज सॉर्ट को उतने पास की आवश्यकता नहीं हो सकती है क्योंकि मर्ज करने के लिए कम रन होते हैं। सबसे अच्छे स्थितियों में, इनपुट पहले से ही क्रमबद्ध होता है (अर्थात यह रन होता है), इसलिए प्राकृतिक मर्ज सॉर्ट को डेटा के माध्यम से केवल पास बनाने की आवश्यकता है। कई व्यावहारिक स्थितियों में, लंबे प्राकृतिक रन उपस्थित होते हैं, और इस कारण से [[टिमसोर्ट]] के प्रमुख घटक के रूप में प्राकृतिक मर्ज सॉर्ट का उपयोग किया जाता है। उदाहरण:
+ 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)
+औपचारिक रूप से, प्राकृतिक मर्ज सॉर्ट को [[एम-इष्टतम छँटाई|रन-इष्टतम]] कहा जाता है, जहाँ <math>\mathtt{Runs}(L)</math> में रनों की संख्या <math>L</math>, से  कम होती है।
-[[टूर्नामेंट छँटाई]] का उपयोग बाहरी छँटाई एल्गोरिदम के लिए प्रारंभिक रन इकट्ठा करने के लिए किया जाता है।
+[[टूर्नामेंट छँटाई|टूर्नामेंट]] सॉर्ट का उपयोग बाहरी सॉर्ट एल्गोरिदम के लिए प्रारंभिक रन इकट्ठा करने के लिए किया जाता है।
 == पिंग-पोंग मर्ज सॉर्ट ==
-समय में दो ब्लॉकों को मर्ज करने के बजाय,  पिंग-पोंग मर्ज  समय में चार ब्लॉकों को मर्ज करता है। चार सॉर्ट किए गए ब्लॉकों को  साथ सहायक स्थान में दो सॉर्ट किए गए ब्लॉकों में मिला दिया जाता है, फिर दो सॉर्ट किए गए ब्लॉकों को वापस मुख्य मेमोरी में मर्ज कर दिया जाता है। ऐसा करने से कॉपी ऑपरेशन छूट जाता है और चालों की कुल संख्या आधी हो जाती है। 2014 में विकीसॉर्ट द्वारा चार-पर- बार विलय का प्रारंभिक सार्वजनिक डोमेन कार्यान्वयन किया गया था, उस वर्ष बाद में विधि को [[धैर्य छँटाई]] के लिए  अनुकूलन के रूप में वर्णित किया गया था और इसे पिंग-पोंग विलय का नाम दिया गया था।<ref name="wikisort">{{cite web
+दो ब्लॉकों को साथ मर्ज करने की अतिरिक्त, पिंग-पोंग मर्ज चार ब्लॉकों को साथ मर्ज करता है। चार सॉर्ट किए गए ब्लॉकों को साथ सहायक स्थान में दो सॉर्ट किए गए ब्लॉकों में मिला दिया जाता है, फिर दो सॉर्ट किए गए ब्लॉकों को वापस मुख्य मेमोरी में मर्ज कर दिया जाता है। इस प्रक्रिया से कॉपी ऑपरेशन को छोड़ा जाता है और कुल मूव की संख्या को आधा कर दिया जाता है। 2014 में विकीसॉर्ट ने चार-एक-साथ मर्ज का पब्लिक डोमेन अंतर्गत अमल में लाया गया था, यह कार्यपद्धति बाद में [[धैर्य छँटाई|धैर्य]] सॉर्टिंग के लिए अनुकूलन के रूप में वर्णित किया गया था और इसे पिंग-पोंग मर्ज का नाम दिया गया था।<ref name="wikisort">{{cite web
   |title       = WikiSort. Fast and stable sort algorithm that uses O(1) memory. Public domain.
   |url         = https://github.com/BonzaiThePenguin/WikiSort
   |last        = |date=14 Apr 2014
-}}</ref><ref>{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014 |url=http://research.microsoft.com/pubs/209622/patsort-sigmod14.pdf}}</ref> Quadsort ने इस मेथड को 2020 में लागू किया और इसे Quad Merge का नाम दिया।<ref name="quadsort">{{cite web
+}}</ref><ref>{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014 |url=http://research.microsoft.com/pubs/209622/patsort-sigmod14.pdf}}</ref> क्वादसोर्ट ने 2020 में इस कार्यपद्धति को अमल में लाया और उसे क्वाड मर्ज के नाम से जाना जाता है।<ref name="quadsort">{{cite web
   |title       = Quadsort is a branchless stable adaptive merge sort.
   |url         = https://github.com/scandum/quadsort
   |last        = |date=8 Jun 2022
 }}</ref>
 == इन-प्लेस मर्ज सॉर्ट ==
-सरणियों पर लागू किए जाने पर मर्ज सॉर्ट का  दोष यह है {{math|''O''(''n'')}} कार्यशील स्मृति आवश्यकताएँ। मेमोरी को कम करने या मर्ज सॉर्ट को पूरी तरह से [[इन-प्लेस एल्गोरिदम]] | इन-प्लेस बनाने के लिए कई तरीके सुझाए गए हैं:
+मर्ज सॉर्ट का दोष, जब सरणियों पर लागू किया जाता है, तो इसकी {{math|''O''(''n'')}} कार्यशील मेमोरी आवश्यकता होती है। मेमोरी को कम करने या मर्ज सॉर्ट को पूरी प्रकार से [[इन-प्लेस एल्गोरिदम]] बनाने के लिए कई विधि सुझाए गए हैं:
-* {{Harvtxt|Kronrod|1969}} निरंतर अतिरिक्त स्थान का उपयोग करने वाले मर्ज सॉर्ट के वैकल्पिक संस्करण का सुझाव दिया।
+* {{Harvtxt|क्रोनरोड |1969}} ने मर्ज सॉर्ट का वैकल्पिक संस्करण सुझाया जो निरंतर अतिरिक्त स्थान का उपयोग करता है।
-* कटजैनेन एट अल।  एल्गोरिथ्म प्रस्तुत करें जिसके लिए निरंतर मात्रा में कार्यशील मेमोरी की आवश्यकता होती है: इनपुट ऐरे के  तत्व को रखने के लिए पर्याप्त स्टोरेज स्पेस, और होल्ड करने के लिए अतिरिक्त स्थान {{math|''O''(1)}} इनपुट ऐरे में पॉइंटर्स। वे  हासिल करते हैं {{math|''O''(''n'' log ''n'')}} छोटे स्थिरांक के साथ समयबद्ध, लेकिन उनका एल्गोरिथ्म स्थिर नहीं है।<ref>{{harvtxt|Katajainen|Pasanen|Teuhola|1996}}</ref>
+* कटजैनेन एट अल. एल्गोरिथ्म प्रस्तुत करें जिसके लिए निरंतर मात्रा में कार्यशील मेमोरी की आवश्यकता होती है: इनपुट ऐरे के तत्व को रखने के लिए पर्याप्त स्टोरेज स्पेस, और होल्ड करने के लिए अतिरिक्त स्थान {{math|''O''(1)}} इनपुट ऐरे में पॉइंटर्स। वे प्राप्त करते हैं। छोटे स्थिरांक के साथ समयबद्ध {{math|''O''(''n'' log ''n'')}} प्राप्त करते हैं, किन्तु उनका एल्गोरिथ्म स्थिर नहीं है।<ref>{{harvtxt|Katajainen|Pasanen|Teuhola|1996}}</ref>
-* इन-प्लेस मर्ज एल्गोरिथम तैयार करने के लिए कई प्रयास किए गए हैं जिन्हें  इन-प्लेस मर्ज सॉर्ट तैयार करने के लिए  मानक (टॉप-डाउन या बॉटम-अप) मर्ज सॉर्ट के साथ जोड़ा जा सकता है। इस मामले में, इन-प्लेस की धारणा को लॉगरिदमिक स्टैक स्पेस लेने के लिए आराम दिया जा सकता है, क्योंकि मानक मर्ज सॉर्ट को अपने स्वयं के स्टैक उपयोग के लिए उस स्थान की आवश्यकता होती है। यह गेफर्ट एट अल द्वारा दिखाया गया था। कि इन-प्लेस में स्थिर विलय संभव है {{math|''O''(''n'' log ''n'')}} स्क्रैच स्पेस की निरंतर मात्रा का उपयोग करते हुए समय, लेकिन उनका एल्गोरिथ्म जटिल है और इसमें उच्च स्थिर कारक हैं: लंबाई की सरणियों का विलय {{mvar|n}} और {{mvar|m}} ले जा सकते हैं {{math|5''n'' + 12''m'' + ''o''(''m'')}} चलता है।<ref>{{Cite journal | doi = 10.1016/S0304-3975(98)00162-5| title = Asymptotically efficient in-place merging| journal = Theoretical Computer Science| volume = 237| pages = 159–181| year = 2000| last1 = Geffert | first1 = Viliam| last2 = Katajainen | first2 = Jyrki| last3 = Pasanen | first3 = Tomi| issue = 1–2| doi-access = free}}</ref> इस उच्च स्थिर कारक और जटिल इन-प्लेस एल्गोरिदम को सरल और समझने में आसान बनाया गया था। बिंग-चाओ हुआंग और माइकल ए. लैंगस्टन<ref name="Research Contributions">{{cite journal |first1=Bing-Chao |last1=Huang |first2=Michael A. |last2=Langston |title=Practical In-Place Merging |date=March 1988 |journal=Communications of the ACM |volume=31 |issue=3 |pages=348–352 |doi=10.1145/42392.42403|s2cid=4841909 |doi-access=free }}</ref> अतिरिक्त स्थान की निश्चित मात्रा का उपयोग करके क्रमबद्ध सूची को मर्ज करने के लिए  सीधा रैखिक समय एल्गोरिदम व्यावहारिक इन-प्लेस मर्ज प्रस्तुत किया। उन दोनों ने क्रोनरोड और अन्य के काम का इस्तेमाल किया है। यह रैखिक समय और निरंतर अतिरिक्त स्थान में विलीन हो जाता है। एल्गोरिथ्म मानक मर्ज सॉर्ट एल्गोरिदम की तुलना में थोड़ा अधिक औसत समय लेता है, O(n) अस्थायी अतिरिक्त मेमोरी कोशिकाओं का दोहन करने के लिए दो से कम कारक से मुक्त होता है। हालांकि एल्गोरिथ्म व्यावहारिक रूप से बहुत तेज है लेकिन यह कुछ सूचियों के लिए अस्थिर भी है। लेकिन इसी तरह की अवधारणाओं का उपयोग करके वे इस समस्या को हल करने में सक्षम हैं। अन्य इन-प्लेस एल्गोरिदम में सिममर्ज शामिल है, जो लेता है {{math|''O''((''n'' + ''m'') log (''n'' + ''m''))}} कुल समय और स्थिर है।<ref>{{Cite conference| doi = 10.1007/978-3-540-30140-0_63| chapter = Stable Minimum Storage Merging by Symmetric Comparisons| conference = European Symp. Algorithms| volume = 3221| pages = 714–723| series = Lecture Notes in Computer Science| year = 2004| last1 = Kim | first1 = Pok-Son| last2 = Kutzner | first2 = Arne| title = Algorithms – ESA 2004| isbn = 978-3-540-23025-0| citeseerx=10.1.1.102.4612}}</ref> इस तरह के  एल्गोरिथ्म को मर्ज सॉर्ट में प्लग करने से इसकी जटिलता गैर-रैखिक रूप से बढ़ जाती है, लेकिन फिर भी [[चतुर्रेखीय समय]], {{math|''O''(''n'' (log ''n'')<sup>2</sup>)}}.
+* इन-प्लेस मर्ज एल्गोरिथम तैयार करने के लिए कई प्रयास किए गए हैं जिन्हें इन-प्लेस मर्ज सॉर्ट तैयार करने के लिए मानक (टॉप-डाउन या बॉटम-अप) मर्ज सॉर्ट के साथ जोड़ा जा सकता है। इस स्थितियों में, इन-प्लेस की धारणा को लॉगरिदमिक स्टैक स्पेस लेने के लिए आराम दिया जा सकता है, क्योंकि मानक मर्ज सॉर्ट को अपने स्वयं के स्टैक उपयोग के लिए उस स्थान की आवश्यकता होती है। यह गेफर्ट एट अल द्वारा दिखाया गया था। कि इन-प्लेस में स्थिर मर्ज संभव है {{math|''O''(''n'' log ''n'')}} स्क्रैच स्पेस की निरंतर मात्रा का उपयोग करते हुए समय, किन्तु उनका एल्गोरिथ्म जटिल है और इसमें उच्च स्थिर कारक हैं: लंबाई की सरणियों का मर्ज {{mvar|n}} और {{mvar|m}} ले जा सकते हैं {{math|5''n'' + 12''m'' + ''o''(''m'')}} चलता है।<ref>{{Cite journal | doi = 10.1016/S0304-3975(98)00162-5| title = Asymptotically efficient in-place merging| journal = Theoretical Computer Science| volume = 237| pages = 159–181| year = 2000| last1 = Geffert | first1 = Viliam| last2 = Katajainen | first2 = Jyrki| last3 = Pasanen | first3 = Tomi| issue = 1–2| doi-access = free}}</ref> इस उच्च स्थिर कारक और जटिल इन-प्लेस एल्गोरिदम को सरल और समझने में आसान बनाया गया था। बिंग-चाओ हुआंग और माइकल ए. लैंगस्टन<ref name="Research Contributions">{{cite journal |first1=Bing-Chao |last1=Huang |first2=Michael A. |last2=Langston |title=Practical In-Place Merging |date=March 1988 |journal=Communications of the ACM |volume=31 |issue=3 |pages=348–352 |doi=10.1145/42392.42403|s2cid=4841909 |doi-access=free }}</ref> अतिरिक्त स्थान की निश्चित मात्रा का उपयोग करके क्रमबद्ध सूची को मर्ज करने के लिए सीधा रैखिक समय एल्गोरिदम व्यावहारिक इन-प्लेस मर्ज प्रस्तुत किया। उन दोनों ने क्रोनरोड और अन्य के काम का उपयोग किया है। यह रैखिक समय और निरंतर अतिरिक्त स्थान में विलीन हो जाता है। एल्गोरिथ्म मानक मर्ज सॉर्ट एल्गोरिदम की समानता में थोड़ा अधिक औसत समय लेता है, इस प्रकार O(n) अस्थायी अतिरिक्त मेमोरी कोशिकाओं का दोहन करने के लिए दो से कम कारक से मुक्त होता है। चूंकि एल्गोरिथ्म व्यावहारिक रूप से बहुत तेज है किन्तु यह कुछ सूचियों के लिए अस्थिर भी है। किन्तु इसी प्रकार की अवधारणाओं का उपयोग करके वे इस समस्या को हल करने में सक्षम हैं। अन्य इन-प्लेस एल्गोरिदम में सिममर्ज सम्मलित है, जो लेता है {{math|''O''((''n'' + ''m'') log (''n'' + ''m''))}} कुल समय और स्थिर है।<ref>{{Cite conference| doi = 10.1007/978-3-540-30140-0_63| chapter = Stable Minimum Storage Merging by Symmetric Comparisons| conference = European Symp. Algorithms| volume = 3221| pages = 714–723| series = Lecture Notes in Computer Science| year = 2004| last1 = Kim | first1 = Pok-Son| last2 = Kutzner | first2 = Arne| title = Algorithms – ESA 2004| isbn = 978-3-540-23025-0| citeseerx=10.1.1.102.4612}}</ref> इस प्रकार के एल्गोरिथ्म को मर्ज सॉर्ट में प्लग करने से इसकी जटिलता गैर-रैखिक रूप से बढ़ जाती है, किन्तु फिर भी [[चतुर्रेखीय समय]], {{math|''O''(''n'' (log ''n'')<sup>2</sup>)}}.
-* [[बाहरी छँटाई]] के कई अनुप्रयोग मर्ज छँटाई के  रूप का उपयोग करते हैं जहाँ इनपुट अधिक संख्या में सबलिस्ट तक विभाजित हो जाता है, आदर्श रूप से  संख्या जिसके लिए उन्हें विलय करने से अभी भी वर्तमान में संसाधित पृष्ठ (कंप्यूटर मेमोरी) का सेट मुख्य मेमोरी में फिट हो जाता है।
+* इस प्रकार [[बाहरी छँटाई|बाहरी]] सॉर्टिंग के कई अनुप्रयोग मर्ज सॉर्ट के रूप का उपयोग करते हैं जहाँ इनपुट अधिक संख्या में उप-सूचियों तक विभाजित हो जाता है, आदर्श रूप से संख्या जिसके लिए उन्हें मर्ज करने से अभी भी वर्तमान में संसाधित पृष्ठ (कंप्यूटर मेमोरी) का सेट मुख्य मेमोरी में फिट हो जाता है।
-* आधुनिक स्थिर रैखिक और इन-प्लेस मर्ज वैरिएंट [[ब्लॉक मर्ज सॉर्ट]] है जो स्वैप स्पेस के रूप में उपयोग करने के लिए अद्वितीय मानों का  खंड बनाता है।
+* आधुनिक स्थिर रैखिक और इन-प्लेस मर्ज वैरिएंट [[ब्लॉक मर्ज सॉर्ट]] है जो स्वैप स्पेस के रूप में उपयोग करने के लिए अद्वितीय मानों का अनुभाग बनाता है।
-* बाइनरी खोजों और घुमावों का उपयोग करके अंतरिक्ष ओवरहेड को sqrt (n) तक कम किया जा सकता है।<ref>{{cite web
+* बाइनरी सेअर्चेस और रोटेशन्स का उपयोग करके अंतरिक्ष ओवरहेड को sqrt (n) तक कम किया जा सकता है।<ref>{{cite web
   |title       = A New Method for Efficient in-Place Merging
   |url         = https://koreascience.kr/article/CFKO200311922203087.page
   |last        = |date=1 Sep 2003
-}}</ref> यह विधि सी ++ एसटीएल लाइब्रेरी और क्वाडोर्ट द्वारा नियोजित है।<ref name="quadsort">{{cite web
+}}</ref> यह विधि C ++ STL लाइब्रेरी और क्वाडोर्ट द्वारा नियोजित है।<ref name="quadsort">{{cite web
   |title       = Quadsort is a branchless stable adaptive merge sort.
   |url         = https://github.com/scandum/quadsort
   |last        = |date=8 Jun 2022
 }}</ref>
-* एकाधिक सूचियों में नकल को कम करने का  विकल्प सूचना के  नए क्षेत्र को प्रत्येक कुंजी के साथ जोड़ना है (एम में तत्वों को कुंजियाँ कहा जाता है)। इस फ़ील्ड का उपयोग सॉर्ट की गई सूची में कुंजियों और किसी भी संबंधित जानकारी को  साथ लिंक करने के लिए किया जाएगा ( कुंजी और उससे संबंधित जानकारी को रिकॉर्ड कहा जाता है)। फिर लिंक मानों को बदलकर सॉर्ट की गई सूचियों का विलय आगे बढ़ता है; किसी भी रिकॉर्ड को स्थानांतरित करने की आवश्यकता नहीं है।  फ़ील्ड जिसमें केवल  लिंक होता है, आम तौर पर पूरे रिकॉर्ड से छोटा होता है इसलिए कम जगह का भी उपयोग किया जाएगा। यह  मानक सॉर्टिंग तकनीक है, जो मर्ज सॉर्ट तक सीमित नहीं है।
+* एकाधिक सूचियों में नकल को कम करने का विकल्प सूचना के नए क्षेत्र को प्रत्येक कुंजी के साथ जोड़ना है (एम में तत्वों को कुंजियाँ कहा जाता है)। इस फ़ील्ड का उपयोग सॉर्ट की गई सूची में कुंजियों और किसी भी संबंधित जानकारी को साथ लिंक करने के लिए किया जाएगा ( कुंजी और उससे संबंधित जानकारी को रिकॉर्ड कहा जाता है)। फिर लिंक मानों को बदलकर सॉर्ट की गई सूचियों का मर्ज आगे बढ़ता है; किसी भी रिकॉर्ड को स्थानांतरित करने की आवश्यकता नहीं है। फ़ील्ड जिसमें केवल लिंक होता है, सामान्यतः पूरे रिकॉर्ड से छोटा होता है इसलिए कम जगह का भी उपयोग किया जाएगा। यह मानक सॉर्टिंग कार्यपद्धति है, जो मर्ज सॉर्ट तक सीमित नहीं है।
-* स्पेस ओवरहेड को n/2 तक कम करने का  सरल तरीका  संयुक्त संरचना के रूप में बाएं और दाएं को बनाए रखना है, केवल m के बाएं हिस्से को अस्थायी स्थान में कॉपी करना है, और मर्ज किए गए आउटपुट को m में रखने के लिए मर्ज रूटीन को निर्देशित करना है। इस संस्करण के साथ मर्ज रूटीन के बाहर अस्थायी स्थान आवंटित करना बेहतर है, ताकि केवल  आवंटन की आवश्यकता हो। पहले बताई गई अत्यधिक नकल को भी कम किया गया है, क्योंकि रिटर्न रिजल्ट स्टेटमेंट (उपरोक्त छद्म कोड में फ़ंक्शन मर्ज) से पहले लाइनों की अंतिम जोड़ी अतिश्योक्तिपूर्ण हो जाती है।
+* स्पेस ओवरहेड को n/2 तक कम करने का सरल प्रणाली संयुक्त संरचना के रूप में बाएं और दाएं को बनाए रखना है, केवल m के बाएं भाग को अस्थायी स्थान में कॉपी करना है, और मर्ज किए गए आउटपुट को m में रखने के लिए मर्ज रूटीन को निर्देशित करना है। इस संस्करण के साथ मर्ज रूटीन के बाहर अस्थायी स्थान आवंटित करना उत्तम है, जिससे केवल आवंटन की आवश्यकता हो। पहले बताई गई अत्यधिक नकल को भी कम किया गया है, क्योंकि रिटर्न रिजल्ट स्टेटमेंट (उपरोक्त छद्म कोड में फ़ंक्शन मर्ज) से पहले लाइनों की अंतिम जोड़ी अतिश्योक्तिपूर्ण हो जाती है।
 == टेप ड्राइव के साथ प्रयोग करें ==
-[[File:IBM 729 Tape Drives.nasa.jpg|thumb|मर्ज सॉर्ट प्रकार के एल्गोरिदम ने बड़े डेटा सेट को शुरुआती कंप्यूटरों पर सॉर्ट करने की अनुमति दी थी, जिनमें आधुनिक मानकों द्वारा छोटी रैंडम एक्सेस मेमोरी थी। रिकॉर्ड [[चुंबकीय टेप]] पर संग्रहीत किए गए थे और चुंबकीय टेप ड्राइव के किनारों पर संसाधित किए गए थे, जैसे कि ये [[IBM 729]]s।]]बाहरी सॉर्टिंग मर्ज सॉर्ट [[डिस्क भंडारण]] या [[टेप ड्राइव]] ड्राइव का उपयोग करने के लिए व्यावहारिक है जब सॉर्ट किया जाने वाला डेटा [[प्रारंभिक भंडारण]] में फ़िट होने के लिए बहुत बड़ा होता है। बाहरी सॉर्टिंग बताती है कि डिस्क ड्राइव के साथ मर्ज सॉर्ट कैसे कार्यान्वित किया जाता है।  विशिष्ट टेप ड्राइव प्रकार चार टेप ड्राइव का उपयोग करता है। सभी I/O अनुक्रमिक हैं (प्रत्येक पास के अंत में रिवाइंड को छोड़कर)। केवल दो रिकॉर्ड बफ़र्स और कुछ प्रोग्राम चर के साथ  न्यूनतम कार्यान्वयन प्राप्त किया जा सकता है।
+[[File:IBM 729 Tape Drives.nasa.jpg|thumb|मर्ज सॉर्ट प्रकार के एल्गोरिदम ने बड़े डेटा सेट को प्रारंभिक कंप्यूटरों पर सॉर्ट करने की अनुमति दी थी, जिनमें आधुनिक मानकों द्वारा छोटी रैंडम एक्सेस मेमोरी थी। रिकॉर्ड [[चुंबकीय टेप]] पर संग्रहीत किए गए थे और चुंबकीय टेप ड्राइव के किनारों पर संसाधित किए गए थे, जैसे कि ये [[IBM 729]]s।]]जब सॉर्ट करने के लिए डेटा मेमोरी में फिट कराना संभव नहीं होता है तो [[डिस्क भंडारण|डिस्क]] या [[टेप ड्राइव]] का उपयोग करके एक्सटर्नल मर्ज सॉर्ट को चलाना संभव होता है। एक्सटर्नल सॉर्टिंग व्यक्त करती है कि मर्ज सॉर्ट को डिस्क ड्राइव के साथ कैसे लागू किया जाता है। इस प्रकार प्रामाणिक टेप ड्राइव सॉर्ट चार टेप ड्राइव का उपयोग करती है। सभी I/O क्रमबद्ध होती है (पास के अंत में रिवाइंड को छोड़कर)।  न्यूनतम कार्यान्वयन केवल दो रिकॉर्ड बफर्स और कुछ प्रोग्राम चरों के साथ हो सकता है।
-ए, बी, सी, डी के रूप में चार टेप ड्राइव का नामकरण, ए पर मूल डेटा के साथ, और केवल दो रिकॉर्ड बफ़र्स का उपयोग करते हुए, एल्गोरिथ्म #नीचे-ऊपर_कार्यान्वयन|नीचे-ऊपर कार्यान्वयन के समान है, बजाय टेप ड्राइव के जोड़े का उपयोग करके स्मृति में सरणियों की। मूल एल्गोरिथ्म को निम्नानुसार वर्णित किया जा सकता है:
+चार टेप ड्राइव को A, B, C, D के रूप में नामित करके, मूल डेटा को A पर रखकर, केवल दो रिकॉर्ड बफर्स का उपयोग करते हुए, एल्गोरिदम बॉटम-अप कार्यान्वयन के समान होता है, मेमोरी में एरे के स्थान पर टेप ड्राइव के जोड़ों का उपयोग करते हुए। मूल एल्गोरिदम को निम्नप्रकार से वर्णित किया जा सकता है:
-# ए से रिकॉर्ड्स के जोड़े को मर्ज करें; सी और डी को वैकल्पिक रूप से दो-रिकॉर्ड सबलिस्ट लिखना।
+# A से रेकॉर्डों के जोड़ों को मर्ज करें; दो-रेकॉर्ड उपसूचियों को C और D में एकान्तरित रूप से लिखें।
-# सी और डी से दो-रिकॉर्ड सब्लिस्ट्स को चार-रिकॉर्ड सब्लिस्ट्स में मर्ज करें; इन्हें A और B में बारी-बारी से लिखते हैं।
+# C और D से दो-रेकॉर्ड उपसूचियों को चार-रेकॉर्ड उपसूचियों में मर्ज करें; इन्हें एकान्तरित रूप से A और B में लिखें।
-# ए और बी से चार-रिकॉर्ड उप-सूचियों को आठ-रिकॉर्ड उप-सूचियों में मर्ज करें; इन्हें बारी-बारी से सी और डी में लिखना
+# A और B से चार-रेकॉर्ड उपसूचियों को आठ-रेकॉर्ड उपसूचियों में मर्ज करें; इन्हें एकान्तरित रूप से C और D में लिखें।
-# तब तक दोहराएं जब तक आपके पास सभी डेटा वाली  सूची न हो, लॉग में सॉर्ट किया गया हो<sub>2</sub>(एन) गुजरता है।
+# इस प्रक्रिया को बार-दो-बार पुनरावृत्ति करें, जब तक आपके पास सभी डेटा को ही सूची में, log<sub>2</sub>(''n'') पास में सॉर्ट करने वाली डेटा हो जाए।
-बहुत कम रनों से शुरू करने के बजाय, आमतौर पर  [[हाइब्रिड एल्गोरिदम]] का उपयोग किया जाता है, जहां प्रारंभिक पास स्मृति में कई रिकॉर्ड पढ़ेगा,  लंबी दौड़ बनाने के लिए  आंतरिक सॉर्ट करेगा, और फिर उन लंबे रनों को आउटपुट सेट पर वितरित करेगा। कदम कई शुरुआती पास से बचा जाता है। उदाहरण के लिए, 1024 रिकॉर्ड्स का आंतरिक सॉर्ट नौ पास बचाएगा। आंतरिक छंटाई अक्सर बड़ी होती है क्योंकि इसका ऐसा लाभ होता है। वास्तव में, ऐसी तकनीकें हैं जो प्रारंभिक रन को उपलब्ध आंतरिक मेमोरी से अधिक लंबा बना सकती हैं। उनमें से एक, नुथ का 'स्नोप्लो' ([[द्विआधारी ढेर]]|बाइनरी मिन-हीप पर आधारित), उपयोग की गई मेमोरी के आकार के रूप में दो बार (औसतन) रन बनाता है।<ref>{{citation| last=Ferragina| first=Paolo| title=The magic of Algorithms!| chapter=5. Sorting Atomic Items| page=5-4| chapter-url=http://didawiki.cli.di.unipi.it/lib/exe/fetch.php/magistraleinformaticanetworking/ae/ae2018/ferragina_notes_algoeng_2019_vers_5_.pdf| date=2009–2019| archive-url=https://web.archive.org/web/20210512230253/http://didawiki.cli.di.unipi.it/lib/exe/fetch.php/magistraleinformaticanetworking/ae/ae2018/ferragina_notes_algoeng_2019_vers_5_.pdf| archive-date=2021-05-12| url-status=live}}</ref>
+बहुत कम रन्स के साथ प्रारंभ करने की अतिरिक्त, सामान्यतः [[हाइब्रिड एल्गोरिदम]] का उपयोग किया जाता है,इस प्रकार जहां प्रारंभिक पास में बहुत सारे रेकॉर्ड्स को मेमोरी में पढ़ाया जाता है, उन्हें आंतरिक सॉर्ट किया जाता है जिससे लंबा रन बनाया जा सके, और फिर वे लंबे रन्स को आउटपुट सेट पर वितरित किए जाते हैं। यह स्टेप कई पहले के पास को बचाता है। उदाहरण के लिए, 1024 रेकॉर्ड का आंतरिक सॉर्ट नौ पास बचा देगा। आंतरिक सॉर्ट अधिकांशतः बड़ा होता है क्योंकि इसमें इतना लाभ होता है। वास्तव में, ऐसी तकनीकें हैं जो प्रारंभिक रन्स को उपलब्ध आंतरिक मेमोरी से भी लंबा बना सकती हैं। उनमें से एक, क्नूथ का 'स्नोप्लो' ([[द्विआधारी ढेर]], बाइनरी मिन-हीप पर आधारित), औसतन मेमोरी के उपयोग के साइज़ के दोगुना लंबे रन्स उत्पन्न करता है।<ref>{{citation| last=Ferragina| first=Paolo| title=The magic of Algorithms!| chapter=5. Sorting Atomic Items| page=5-4| chapter-url=http://didawiki.cli.di.unipi.it/lib/exe/fetch.php/magistraleinformaticanetworking/ae/ae2018/ferragina_notes_algoeng_2019_vers_5_.pdf| date=2009–2019| archive-url=https://web.archive.org/web/20210512230253/http://didawiki.cli.di.unipi.it/lib/exe/fetch.php/magistraleinformaticanetworking/ae/ae2018/ferragina_notes_algoeng_2019_vers_5_.pdf| archive-date=2021-05-12| url-status=live}}</ref>
-कुछ ओवरहेड के साथ, उपरोक्त एल्गोरिथ्म को तीन टेपों का उपयोग करने के लिए संशोधित किया जा सकता है। ओ (एन लॉग एन) चलने का समय दो कतार (सार डेटा प्रकार), या  ढेर (सार डेटा प्रकार) और  कतार, या तीन ढेर का उपयोग करके भी प्राप्त किया जा सकता है। दूसरी दिशा में, k > दो टेप (और मेमोरी में O(k) आइटम) का उपयोग करके, हम k-way मर्ज एल्गोरिथम|k/2-way का उपयोग करके O(log k) समय में टेप संचालन की संख्या को कम कर सकते हैं। विलय।
+ऊपरी एल्गोरिदम में कुछ ओवरहेड के साथ, तीन टेप्स का उपयोग किया जा सकता है। O (n log n) चलने का समय दो कतारों, या स्टैक और कतार, या तीन स्टैक्स का उपयोग करके भी प्राप्त किया जा सकता है। दूसरी दिशा में, k > दो टेप्स (और O(k) आइटम मेमोरी में) का उपयोग करके, हम k/2-वे मर्ज का उपयोग करके O(log k) बार में टेप आपरेशन की संख्या को कम कर सकते हैं।
 अधिक परिष्कृत मर्ज सॉर्ट जो टेप (और डिस्क) ड्राइव के उपयोग को अनुकूलित करता है, वह [[पॉलीफ़ेज़ मर्ज सॉर्ट]] है।
 == मर्ज सॉर्ट का अनुकूलन ==
-[[Image:Merge sort animation2.gif|thumb|यादृच्छिक पूर्णांकों की  सरणी पर टाइल मर्ज सॉर्ट लागू किया गया। क्षैतिज अक्ष सरणी अनुक्रमणिका है और लंबवत अक्ष पूर्णांक है।]]आधुनिक कंप्यूटरों पर, संदर्भ की स्थानीयता [[सॉफ्टवेयर अनुकूलन]] में सर्वोपरि हो सकती है, क्योंकि बहुस्तरीय [[मेमोरी पदानुक्रम]] का उपयोग किया जाता है। मर्ज सॉर्ट एल्गोरिथम के कैशे (कंप्यूटिंग)-जागरूक संस्करण, जिनके संचालन को विशेष रूप से मशीन के मेमोरी कैश में और बाहर पृष्ठों के संचलन को कम करने के लिए चुना गया है, प्रस्तावित किया गया है। उदाहरण के लिए, द{{visible anchor|tiled merge sort}}एल्गोरिथम आकार S की उपसरणियों तक पहुँचने पर उप-सरणियों का विभाजन बंद कर देता है, जहाँ S CPU के कैश में फिट होने वाले डेटा आइटमों की संख्या है। इनमें से प्रत्येक उप-सरणियों को इन-प्लेस सॉर्टिंग एल्गोरिथम जैसे [[सम्मिलन सॉर्ट]] के साथ क्रमबद्ध किया जाता है, मेमोरी स्वैप को हतोत्साहित करने के लिए, और सामान्य मर्ज सॉर्ट को मानक पुनरावर्ती फैशन में पूरा किया जाता है। इस एल्गोरिथ्म ने बेहतर प्रदर्शन का प्रदर्शन किया है {{Examples|date=August 2016}} उन मशीनों पर जो कैश ऑप्टिमाइज़ेशन से लाभान्वित होती हैं। {{Harv|LaMarca|Ladner|1997}}
+[[Image:Merge sort animation2.gif|thumb|यादृच्छिक पूर्णांकों की सरणी पर टाइल मर्ज सॉर्ट लागू किया गया। क्षैतिज अक्ष सरणी अनुक्रमणिका है और लंबवत अक्ष पूर्णांक है।]]आधुनिक कंप्यूटरों पर, संदर्भ की स्थानीयता [[सॉफ्टवेयर अनुकूलन]] में महत्वपूर्ण हो सकती है, क्योंकि बहुस्तरीय [[मेमोरी पदानुक्रम|मेमोरी हाइयरार्की]] का उपयोग किया जाता है। मर्ज सॉर्ट एल्गोरिदम के कैश-जागरूक संस्करणों की प्रस्तावित की गई हैं, जिनकी कार्रवाई को विशेष रूप से चुना गया है जिससे मशीन की मेमोरी कैश में पेज के आने-जाने को कम किया जा सके। उदाहरण के लिए, टाइल्ड मर्ज सॉर्ट एल्गोरिदम उप-एरे का विभाजन रोक देता है जब एस आकार के उप-एरे पहुंचे जाते हैं, जहां S सीपीयू के कैश में समायोजित करने वाले डेटा आइटमों की संख्या होती है। इनमें से प्रत्येक उप-सरणियों को इन-प्लेस सॉर्टिंग एल्गोरिथम जैसे [[सम्मिलन सॉर्ट|इंसर्शन सॉर्ट]] के साथ क्रमबद्ध किया जाता है, मेमोरी स्वैप को हतोत्साहित करने के लिए, और सामान्य मर्ज सॉर्ट को मानक पुनरावर्ती फैशन में पूर्व किया जाता है। इस एल्गोरिदम ने कैश अनुकूलन से लाभ उठाने वाली मशीनों पर उत्तम प्रदर्शन प्रदर्शित किया है। {{Harv|LaMarca|Ladner|1997}}
+== समानांतर मर्ज सॉर्ट ==
+मर्ज सॉर्ट पूर्वानुमान और विज्ञान में बड़े पैमाने पर पैरललीकरण के लिए उत्कृष्ट होता है क्योंकि यह विभाजन-और-विजयी विधि का उपयोग करता है। इसके अलग-अलग पैरलल वेरिएंट वर्षों से विकसित किए गए हैं। कुछ पैरलल मर्ज सॉर्ट एल्गोरिदम श्रृंगार मौलिक टॉप-डाउन मर्ज एल्गोरिदम से मजबूत रूप से संबंधित हैं चूँकि दूसरे के पास अलग सामान्य संरचना होती है और वे [[के-वे मर्ज एल्गोरिथम]] का उपयोग करते हैं।
+=== समानांतर रिकर्सन के साथ मर्ज सॉर्ट करें ===
+अनुक्रमिक मर्ज सॉर्ट प्रक्रिया को दो चरणों में वर्णित किया जा सकता है, विभाजन चरण और मर्ज चरण। पहला चरण कई रिकर्सिव कॉल्स से मिलकर मिलता है जो बार-बार ही विभाजन प्रक्रिया को प्रदर्शित करते हैं जब तक उपद्रवियों को आसानी से सॉर्ट कर दिया जाता है (जिसमें या कोई भी तत्व होते हैं)। उन रिकर्सिव कॉल्स को पैरललाइज़ करने की संवेदनशील दृष्टिकोण होती है। <ref name="clrs">{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|pp=797–805}}</ref> निम्नलिखित प्यूडोकोड में पैरलल रिकर्सन का उपयोग करके मर्ज सॉर्ट का वर्णन किया गया है जहां फोर्क और ज्वाइन कीवर्ड का उपयोग किया जाता है:
-== समानांतर मर्ज सॉर्ट ==
+ // ''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)
+यह एल्गोरिदम अनुक्रमिक संस्करण का तत्कालीन संशोधन है और इसे पैरललीकरण के लिए उत्कृष्ट नहीं माना जाता है। इसलिए, इसका स्पीडअप बहुत प्रभावशाली नहीं होता है। इसका स्पैन <math>\Theta(n)</math> होता है, जो सीक्वेंशियल संस्करण की समानता में केवल <math>\Theta(\log n)</math> का सुधार है ([[एल्गोरिदम का परिचय]] देखें)। इसका मुख्य कारण सीक्वेंशियल मर्ज मेथड है, क्योंकि यह पैरलल क्रियान्वयनों का बोटलनेक है।
-=== समानांतर पुनरावर्तन === के साथ मर्ज करें
+=== समानांतर विलय के साथ मर्ज सॉर्ट करें ===
-अनुक्रमिक मर्ज सॉर्ट प्रक्रिया को दो चरणों में विभाजित चरण और मर्ज चरण में वर्णित किया जा सकता है। पहले में कई पुनरावर्ती कॉल होते हैं जो बार-बार  ही विभाजन प्रक्रिया को तब तक करते हैं जब तक कि अनुवर्ती छँटाई न हो जाए (जिसमें  या कोई तत्व न हो)।  सहज ज्ञान युक्त दृष्टिकोण उन पुनरावर्ती कॉलों का समानांतरकरण है।<ref name="clrs">{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|pp=797–805}}</ref> निम्नलिखित स्यूडोकोड फोर्क-जॉइन मॉडल कीवर्ड का उपयोग करके समानांतर पुनरावर्तन के साथ मर्ज सॉर्ट का वर्णन करता है:
+{{Main|मर्ज एल्गोरिदम#समानांतर मर्ज}}
- // सरणी ए के हाय (अनन्य) के माध्यम से तत्वों को क्रमबद्ध करें।
+पैरलल मर्ज एल्गोरिदम का उपयोग करके उत्तम पैरललिस्म प्राप्त किया जा सकता है। कॉर्मेन आदि द्वारा बाइनरी चर दर्शाने वाला वेरिएंट प्रस्तुत किया गया है जो दो सॉर्ट किए गए उप-क्रमों को सॉर्ट किए गए आउटपुट क्रम में मर्ज करता है।<ref name="clrs" />
- 'एल्गोरिदम' विलय (ए, लो, हाय) 'है'
-     'अगर' लो + 1 <हाय 'फिर' // दो या दो से अधिक तत्व।
-         मध्य := ⌊(लो + हाय) / 2⌋
-         'फोर्क' विलय (ए, लो, मिड)
-         मर्जसॉर्ट (ए, मिड, हाय)
-         'जोड़ना'
-         मर्ज (ए, लो, मिड, हाय)
-यह एल्गोरिथ्म अनुक्रमिक संस्करण का तुच्छ संशोधन है और अच्छी तरह से समानांतर नहीं होता है। इसलिए, इसका speedup बहुत प्रभावशाली नहीं है। इसमें समानांतर एल्गोरिदम का विश्लेषण # का अवलोकन है <math>\Theta(n)</math>, जो केवल  सुधार है <math>\Theta(\log n)</math> अनुक्रमिक संस्करण की तुलना में ([[एल्गोरिदम का परिचय]] देखें)। यह मुख्य रूप से अनुक्रमिक विलय विधि के कारण है, क्योंकि यह समांतर निष्पादन की बाधा है।
-=== समानांतर मर्जिंग === के साथ मर्ज सॉर्ट करें
+दोनों उप-क्रमों में से में (यदि असमान लंबाई है तो बड़े उप-क्रम में) मध्य अनुक्रम के तत्व को चुना जाता है। इसकी पदावनति दूसरे उप-क्रम में इस प्रकार निर्धारित की जाती है कि यदि इस तत्व को इस पदावनति पर सम्मिलित किया जाता है तो यह उप-क्रम सॉर्ट रहेगा। इस प्रकार, ज्ञात हो जाता है कि दोनों उप-क्रमों से कितने अन्य तत्व छोटे हैं और चयनित तत्व की आउटपुट क्रम में पदावनति की गणना की जा सकती है। इस प्रकार बनाए गए छोटे और बड़े तत्वों के आंशिक क्रमों के लिए, मर्ज एल्गोरिदम को पुनः पैरलल में चलाया जाता है जब तक संघटन के मूल तत्व तक पहुंचा नहीं जाता है।
-{{Main|Merge algorithm#Parallel merge}}
-समांतर विलय एल्गोरिदम का उपयोग करके बेहतर समांतरता प्राप्त की जा सकती है। एल्गोरिद्म का परिचय | कॉर्मेन एट अल।  बाइनरी वेरिएंट प्रस्तुत करें जो दो सॉर्ट किए गए उप-अनुक्रमों को  सॉर्ट किए गए आउटपुट अनुक्रम में मिला देता है।<ref name="clrs" />
-अनुक्रमों में से  में (असमान लंबाई होने पर लंबा), मध्य सूचकांक का तत्व चुना जाता है। अन्य अनुक्रम में इसकी स्थिति इस तरह से निर्धारित की जाती है कि यदि यह तत्व इस स्थिति में डाला जाता है तो यह क्रम क्रमबद्ध रहेगा। इस प्रकार, कोई जानता है कि दोनों अनुक्रमों से कितने अन्य तत्व छोटे हैं और आउटपुट अनुक्रम में चयनित तत्व की स्थिति की गणना की जा सकती है। इस तरह से बनाए गए छोटे और बड़े तत्वों के आंशिक अनुक्रमों के लिए, मर्ज एल्गोरिथम को फिर से समानांतर में तब तक निष्पादित किया जाता है जब तक कि पुनरावर्तन का आधार मामला नहीं हो जाता।
+निम्नलिखित प्यूडोकोड में संशोधित पैरलल मर्ज सॉर्ट विधि दिखाई गई है जो पैरलल मर्ज एल्गोरिदम का उपयोग करती है (कॉर्मेन आदि से लाया गया):-
-निम्नलिखित स्यूडोकोड समानांतर मर्ज एल्गोरिथम (कॉर्मेन एट अल से अपनाया गया) का उपयोग करके संशोधित समानांतर मर्ज सॉर्ट विधि दिखाता है।
   /**
-   * ए: इनपुट सरणी
+   * A: Input array
-   * बी: आउटपुट सरणी
+   * B: Output array
-   * लो: निचली सीमा
+   * lo: lower bound
-   * हाय: ऊपरी सीमा
+   * hi: upper bound
-   * ऑफ: ऑफसेट
+   * off: offset
    */
-  एल्गोरिथ्म समानांतर मेर्जेसॉर्ट (ए, लो, हाय, बी, ऑफ) है
+  '''algorithm''' parallelMergesort(A, lo, hi, B, off) '''is'''
-      लेन�:= हि - लो + 1
+      len := hi - lo + 1
-      अगर लेन == 1 तब
+      '''if''' len == 1 '''then'''
- <nowiki> B[off] := A[lo]</nowiki>
+         B[off] := A[lo]
-      वरना T[1..len]  नई सरणी होने दें
+      '''else''' let T[1..len] be a new array
-          मध्य�:= ⌊(लो + हाय) / 2⌋
+          mid := ⌊(lo + hi) / 2⌋
-          मध्य'�:= मध्य - लो + 1
+          mid' := mid - lo + 1
-          कांटा समानांतर मेर्जेसॉर्ट (ए, लो, मिड, टी, 1)
+          '''fork''' parallelMergesort(A, lo, mid, T, 1)
-          पैरेलल मेर्जेसॉर्ट (ए, मिड + 1, हाय, टी, मिड' + 1)
+          parallelMergesort(A, mid + 1, hi, T, mid' + 1)
-          जोड़ना
+          '''join'''
-          समांतर मर्ज (टी, 1, मिड ', मिड' + 1, लेन, बी, ऑफ)
+          parallelMerge(T, 1, mid', mid' + 1, len, B, off)
-सबसे खराब केस स्पैन के लिए पुनरावृत्ति संबंध का विश्लेषण करने के लिए, पैरेलल मेर्जेसॉर्ट के रिकर्सिव कॉल को उनके समानांतर निष्पादन के कारण केवल  बार शामिल किया जाना चाहिए, प्राप्त करना
+सबसे बुरी स्थिति अवधि के लिए पुनरावृत्ति संबंध का विश्लेषण करने के लिए, समानांतर मर्जसॉर्ट की पुनरावर्ती कॉल को उनके समानांतर निष्पादन के कारण केवल सम्मलित करना होगा, प्राप्त करना होगा
 <math display="block"> 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).</math>
-समांतर विलय प्रक्रिया की जटिलता के बारे में विस्तृत जानकारी के लिए, मर्ज एल्गोरिदम # समांतर विलय देखें।
+समानांतर मर्ज प्रक्रिया की जटिलता के बारे में विस्तृत जानकारी के लिए, मर्ज एल्गोरिदम देखें।
-इस पुनरावृत्ति का हल इसके द्वारा दिया गया है
+इस पुनरावृत्ति का समाधान द्वारा दिया गया है<math display="block"> T_{\infty}^{\text{sort}} = \Theta \left ( \log(n)^3 \right).</math>
+यह समानांतर मर्ज एल्गोरिदम समानता तक पहुंचता है <math display="inline">\Theta \left(\frac{n}{(\log n)^2}\right)</math>, जो पूर्व एल्गोरिथम की समानता से बहुत अधिक है। ऐसा सॉर्ट व्यवहार में अच्छा प्रदर्शन कर सकता है जब इसे तेज स्थिर अनुक्रमिक सॉर्ट, जैसे कि इंसर्शन सॉर्ट, और छोटे सरणियों को मर्ज करने के लिए बेस केस के रूप में तेज अनुक्रमिक मर्ज के साथ जोड़ा जाता है।<ref>Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog [https://duvanenko.tech.blog/2018/01/13/parallel-merge-sort/] and GitHub repo C++ implementation [https://github.com/DragonSpit/ParallelAlgorithms]</ref>
-<math display="block"> T_{\infty}^{\text{sort}} = \Theta \left ( \log(n)^3 \right).</math>
-यह समांतर विलय एल्गोरिदम  समानता तक पहुंचता है <math display="inline">\Theta \left(\frac{n}{(\log n)^2}\right)</math>, जो पिछले एल्गोरिथम की समानता से बहुत अधिक है। इस तरह का  प्रकार व्यवहार में अच्छा प्रदर्शन कर सकता है जब  तेजी से स्थिर अनुक्रमिक सॉर्ट, जैसे सम्मिलन सॉर्ट, और छोटे सरणियों को मर्ज करने के लिए बेस केस के रूप में  तेज अनुक्रमिक मर्ज के साथ जोड़ा जाता है।<ref>Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog [https://duvanenko.tech.blog/2018/01/13/parallel-merge-sort/] and GitHub repo C++ implementation [https://github.com/DragonSpit/ParallelAlgorithms]</ref>
 === समानांतर मल्टीवे मर्ज सॉर्ट ===
-यह मर्ज सॉर्ट एल्गोरिदम को बाइनरी मर्ज विधि तक सीमित करने के लिए मनमाना लगता है, क्योंकि आमतौर पर p > 2 प्रोसेसर उपलब्ध होते हैं। के-वे मर्ज एल्गोरिथम का उपयोग करने के लिए  बेहतर तरीका हो सकता है | के-वे मर्ज विधि, बाइनरी मर्ज का  सामान्यीकरण, जिसमें <math>k</math> क्रमबद्ध अनुक्रमों को मिला दिया जाता है। यह मर्ज वेरिएंट [[समानांतर रैंडम-एक्सेस मशीन]] पर सॉर्टिंग एल्गोरिदम का वर्णन करने के लिए उपयुक्त है।<ref>{{cite web|author1=Peter Sanders |author2=Johannes Singler |date=2008 |title=Lecture ''Parallel algorithms'' |url=http://algo2.iti.kit.edu/sanders/courses/paralg08/singler.pdf |access-date=2020-05-02}}</ref><ref name=":0">{{Cite journal|title=Practical Massively Parallel Sorting |journal=Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures|year=2015|doi=10.1145/2755573.2755595|last1=Axtmann|first1=Michael|last2=Bingmann|first2=Timo|last3=Sanders|first3=Peter|last4=Schulz|first4=Christian|pages=13–23|isbn=9781450335881|s2cid=18249978|url=https://publikationen.bibliothek.kit.edu/1000050651/37296033}}</ref>
+मर्ज सॉर्ट एल्गोरिदम को बाइनरी मर्ज मेथड से सीमित करना एकसंयुक्त प्रोसेसर्स पर काम करने के लिए अनुकूल नहीं हो सकता है, क्योंकि सामान्यतः p > 2 प्रोसेसर्स उपलब्ध होते हैं।  उत्तम दृष्टिकोण हो सकता है कि K-वे मर्ज मेथड का उपयोग करें, जो बाइनरी मर्ज का विस्तार है, जहां <math>k</math> किए गए अनुक्रमों को मर्ज किया जाता है। यह मर्ज वेरिएंट [[समानांतर रैंडम-एक्सेस मशीन]] पर सॉर्टिंग एल्गोरिदम का वर्णन करने के लिए उपयुक्त है।<ref>{{cite web|author1=Peter Sanders |author2=Johannes Singler |date=2008 |title=Lecture ''Parallel algorithms'' |url=http://algo2.iti.kit.edu/sanders/courses/paralg08/singler.pdf |access-date=2020-05-02}}</ref><ref name=":0">{{Cite journal|title=Practical Massively Parallel Sorting |journal=Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures|year=2015|doi=10.1145/2755573.2755595|last1=Axtmann|first1=Michael|last2=Bingmann|first2=Timo|last3=Sanders|first3=Peter|last4=Schulz|first4=Christian|pages=13–23|isbn=9781450335881|s2cid=18249978|url=https://publikationen.bibliothek.kit.edu/1000050651/37296033}}</ref>
 ==== मूल विचार ====
-[[File:Parallel_multiway_mergesort_process.svg|alt=|thumb|चार प्रोसेसरों पर समानांतर मल्टीवे विलय प्रक्रिया <math>t_0</math> को <math>t_3</math>.]]के  अवर्गीकृत अनुक्रम को देखते हुए <math>n</math> तत्वों, लक्ष्य अनुक्रम को क्रमबद्ध करना है <math>p</math> उपलब्ध [[प्रोसेसर (कंप्यूटिंग)]]। इन तत्वों को सभी प्रोसेसरों के बीच समान रूप से वितरित किया जाता है और अनुक्रमिक सॉर्टिंग एल्गोरिदम का उपयोग करके स्थानीय रूप से सॉर्ट किया जाता है। इसलिए, अनुक्रम में क्रमबद्ध अनुक्रम होते हैं <math>S_1, ..., S_p</math> लंबाई का <math display="inline">\lceil \frac{n}{p} \rceil</math>. सरलीकरण के लिए <math>n</math> का गुणक हो <math>p</math>, ताकि <math display="inline">\left\vert S_i \right\vert = \frac{n}{p}</math> के लिए <math>i = 1, ..., p</math>.
+[[File:Parallel_multiway_mergesort_process.svg|alt=|thumb|चार प्रोसेसरों पर समानांतर मल्टीवे मर्ज प्रक्रिया <math>t_0</math> को <math>t_3</math>.]]दिए गए <math>n</math> तत्वों के असंक्योजक क्रम को <math>p</math> उपलब्ध [[प्रोसेसर (कंप्यूटिंग)]] के साथ सॉर्ट करना लक्ष्य है। इन तत्वों को सभी प्रोसेसर्स के बीच समान रूप से वितरित किया जाता है और क्रमशः एकल क्रम में लोकली सॉर्ट किया जाता है। इस प्रकार, क्रमशः सूची में इनपुट सूचियाँ <math>S_1, ..., S_p</math> होती हैं जिनकी लंबाई <math display="inline">\lceil \frac{n}{p} \rceil</math> होती है। सरलीकरण के लिए आपको मान लें कि <math>n</math> का प्रमाणित कर्म <math>p</math>, का गुणक है, जिससे <math display="inline">\left\vert S_i \right\vert = \frac{n}{p}</math> हो, <math>i = 1, ..., p</math> के लिए किया जाता है ।
-इन अनुक्रमों का उपयोग बहु-अनुक्रम चयन/स्प्लिटर चयन करने के लिए किया जाएगा। के लिए <math>j = 1,..., p</math>, एल्गोरिदम स्प्लिटर तत्वों को निर्धारित करता है <math>v_j
+इन सूचियों का उपयोग मल्टीसीक्वेंस चुनाव/स्प्लिटर चुनाव करने के लिए किया जाएगा। <math>j = 1,..., p</math>, के लिए, एल्गोरिदम सार्वभौमिक रैंक <math display="inline">k = j \frac{n}{p}</math> के साथ स्प्लिटर तत्व <math>v_j
-</math> वैश्विक रैंक के साथ <math display="inline">k = j \frac{n}{p}</math>. फिर की इसी स्थिति <math>v_1, ..., v_p</math> प्रत्येक क्रम में <math>S_i</math> [[बाइनरी सर्च एल्गोरिथम]] के साथ निर्धारित किया जाता है और इस प्रकार <math>S_i</math> आगे विभाजित हैं <math>p</math> अनुवर्ती <math>S_{i,1}, ..., S_{i,p}</math> साथ <math display="inline">S_{i,j} := \{x \in S_i | rank(v_{j-1}) < rank(x) \le rank(v_j)\}</math>.
+</math> निर्धारित करता है। फिर हर सूची <math>S_i</math> में <math>v_1, ..., v_p</math> की मान्यता के मानकों की प्रणाली से जांच करके उसकी संबंधित स्थितियों की पता लगाई जाती है, और इस प्रकार <math>S_i</math> को <math>p</math> में विभाजित किया जाता है, जहां <math>S_{i,1}, ..., S_{i,p}</math> के लिए <math display="inline">S_{i,j} := \{x \in S_i | rank(v_{j-1}) < rank(x) \le rank(v_j)\}</math> होता है।
-इसके अलावा, के तत्व <math>S_{1,i}, ..., S_{p,i}</math> प्रोसेसर को सौंपा गया है <math>i</math>, का अर्थ रैंक के बीच के सभी तत्व हैं <math display="inline">(i-1) \frac{n}{p}</math> और रैंक <math display="inline">i \frac{n}{p}</math>, जो सभी में वितरित हैं <math>S_i</math>. इस प्रकार, प्रत्येक प्रोसेसर को क्रमबद्ध अनुक्रमों का क्रम प्राप्त होता है। तथ्य यह है कि रैंक <math>k</math> विभाजक तत्वों की <math>v_i</math> विश्व स्तर पर चुना गया था, दो महत्वपूर्ण गुण प्रदान करता है:  ओर, <math>k</math> चुना गया था ताकि प्रत्येक प्रोसेसर अभी भी काम कर सके <math display="inline">n/p</math> असाइनमेंट के बाद तत्व एल्गोरिथ्म पूरी तरह से [[लोड संतुलन (कंप्यूटिंग)]] | लोड-संतुलित है। दूसरी ओर, प्रोसेसर पर सभी तत्व <math>i</math> प्रोसेसर पर सभी तत्वों से कम या बराबर हैं <math>i+1</math>. इसलिए, प्रत्येक प्रोसेसर के-वे मर्ज एल्गोरिथम | पी-वे मर्ज को स्थानीय रूप से निष्पादित करता है और इस प्रकार इसके उप-अनुक्रमों से क्रमबद्ध अनुक्रम प्राप्त करता है। दूसरी संपत्ति के कारण, कोई और पी-वे-मर्ज नहीं करना पड़ता है, परिणाम केवल प्रोसेसर संख्या के क्रम में  साथ रखे जाते हैं।
+इसके अतिरिक्त, सूची के तत्व <math>S_{1,i}, ..., S_{p,i}</math> को प्रोसेसर <math>i</math>, को सौंपा जाता है, इसका अर्थ है कि सभी तत्वों को रैंक <math display="inline">(i-1) \frac{n}{p}</math> और रैंक <math display="inline">i \frac{n}{p}</math>, के बीच स्थित किया जाता है, जो सभी <math>S_i</math>.पर वितरित होते हैं। इस प्रकार, प्रत्येक प्रोसेसर को सूची सॉर्ट की उप-सूचियों की अनुक्रम सौंपी जाती है। यह तथ्य कि स्प्लिटर तत्वों <math>v_i</math> का रैंक वैश्विक रूप से चुना गया था, दो महत्वपूर्ण गुण प्रदान करता है: एकतरफ़ा, <math>k</math> इस प्रकार चुना गया था कि हर प्रोसेसर को आवंटित करने के बाद भी प्रति <math display="inline">n/p</math> तत्वों पर ऑपरेशन कर सके। एल्गोरिदम पूरी प्रकार से [[लोड संतुलन (कंप्यूटिंग)]] होता है। दूसरी ओर, प्रोसेसर <math>i</math> पर सभी तत्व प्रोसेसर <math>i+1</math> पर सभी तत्वों से छोटे या समान होते हैं। इसलिए, प्रत्येक प्रोसेसर स्वतंत्र रूप से p-वे मर्ज करता है और अपनी उप-सूचियों से क्रमबद्ध सूची प्राप्त करता है। दूसरे गुण के कारण, और कोई अधिक p-वे-मर्ज करने की आवश्यकता नहीं होती है, परिणामों को केवल प्रोसेसर संख्या के क्रम में मिलाने की आवश्यकता होती है।
 ==== बहु-अनुक्रम चयन ====
-अपने सरलतम रूप में, दिया गया <math>p</math> क्रमबद्ध अनुक्रम <math>S_1, ..., S_p</math> पर समान रूप से वितरित <math>p</math> प्रोसेसर और  रैंक <math>k</math>, कार्य  तत्व खोजना है <math>x</math>  वैश्विक रैंक के साथ <math>k</math> अनुक्रमों के मिलन में। इसलिए, इसका उपयोग प्रत्येक को विभाजित करने के लिए किया जा सकता है <math>S_i</math> स्प्लिटर इंडेक्स पर दो भागों में <math>l_i</math>, जहां निचले हिस्से में केवल ऐसे तत्व होते हैं जो इससे छोटे होते हैं <math>x</math>, जबकि तत्वों से बड़ा <math>x</math> ऊपरी भाग में स्थित हैं।
+सरलतम रूप में, दिए गए <math>p</math> क्रमबद्ध सूचियों <math>S_1, ..., S_p</math> को संघटित रूप में इकट्ठा किया गया है जो <math>p</math> प्रोसेसरों पर समान रूप से वितरित हैं, और रैंक <math>k</math>, के साथ तत्व <math>x</math> को खोजने की कार्य है जिसका सार्वभौमिक रैंक <math>k</math> इन सूचियों के संयोजन में होता है। इसलिए, इसका उपयोग किया जा सकता है कि प्रत्येक <math>S_i</math> को स्प्लिटर सूचकांक <math>l_i</math>, पर दो भागों में विभाजित किया जाए, जहां निचला भाग केवल उन तत्वों को सम्मिलित करता है जो <math>x</math> से छोटे हैं, चूँकि <math>x</math> से बड़े तत्व उपरी भाग में स्थित हैं।
-प्रस्तुत अनुक्रमिक एल्गोरिदम प्रत्येक अनुक्रम में विभाजन के सूचकांक लौटाता है, उदा। सूचकांक <math>l_i</math> क्रम में <math>S_i</math> ऐसा है कि <math>S_i[l_i]</math> से कम वैश्विक रैंक है <math>k</math> और <math>\mathrm{rank}\left(S_i[l_i+1]\right) \ge k</math>.<ref>{{cite web |author=Peter Sanders |date=2019 |title=Lecture ''Parallel algorithms'' |url=http://algo2.iti.kit.edu/sanders/courses/paralg19/vorlesung.pdf |access-date=2020-05-02}}</ref>
+प्रस्तुत सीक्वेंशियल एल्गोरिदम प्रत्येक सूची में विभाजनों के सूचकांकों, जैसे सूची में सूचकांक <math>l_i</math> से संबंधित इंडेक्स को लौटाता है जिसके लिए, <math>S_i[l_i]</math> का सार्वभौमिक रैंक <math>k</math> से कम होता है और <math>\mathrm{rank}\left(S_i[l_i+1]\right) \ge k</math>.<ref>{{cite web |author=Peter Sanders |date=2019 |title=Lecture ''Parallel algorithms'' |url=http://algo2.iti.kit.edu/sanders/courses/paralg19/vorlesung.pdf |access-date=2020-05-02}}</ref>होता है।
-एल्गोरिद्म<nowiki> msSelect(S : क्रमबद्ध अनुक्रमों की सरणी [S_1,..,S_p], k : int) </nowiki>है
-      i = 1 से p करने के लिए
+ '''algorithm''' msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) '''is'''
- (l_i, r_i) = (0, |S_i|-1)
+      '''for''' i = 1 '''to''' p '''do'''
+ 	(l_i, r_i) = (0, |S_i|-1)
-      जबकि वहाँ मौजूद है i: l_i < r_i do
- // एस_जे [एल_जे], .., एस_जे [आर_जे] में धुरी तत्व चुनें, समान रूप से यादृच्छिक जे चुना
+      '''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
- i = 1 से p करने के लिए
+ 	v := pickPivot(S, l, r)
- m_i = बाइनरीसर्च (v, S_i [l_i, r_i]) // क्रमिक रूप से
+ 	'''for''' i = 1 '''to''' p '''do'''
- अगर m_1 + ... + m_p >= k तब // m_1+ ... + m_p v की वैश्विक रैंक है
+ 	    m_i = binarySearch(v, S_i[l_i, r_i]) // sequentially
- r := m // वेक्टर असाइनमेंट
+ 	'''if''' m_1 + ... + m_p >= k '''then''' // m_1+ ... + m_p is the global rank of v
- अन्य
+ 	    r := m  // vector assignment
- ल := म
+ 	'''else'''
+ 	    l := m
-      वापसी एल
-जटिलता विश्लेषण के लिए समानांतर रैंडम-एक्सेस मशीन मॉडल चुना जाता है। यदि डेटा समान रूप से सभी पर वितरित किया जाता है <math>p</math>, बाइनरीसर्च पद्धति के पी-फोल्ड निष्पादन का चलने का समय है <math>\mathcal{O}\left(p\log\left(n/p\right)\right)</math>. अपेक्षित पुनरावर्तन गहराई है <math>\mathcal{O}\left(\log\left( \textstyle \sum_i |S_i| \right)\right) = \mathcal{O}(\log(n))</math> जैसा कि सामान्य [[तुरंत चयन]] में होता है। इस प्रकार समग्र अपेक्षित चलने का समय है <math>\mathcal{O}\left(p\log(n/p)\log(n)\right)</math>.
+      '''return''' l
+यदि डेटा सभी <math>p</math>,पर समान रूप से वितरित होता है, तो बाइनरीसर्च विधि का p-गुणन क्रियान्वयन चलने का समय <math>\mathcal{O}\left(p\log\left(n/p\right)\right)</math> होता है। आश्वासनीय रूप से अपेक्षित पुनरावर्तन की गहराई <math>\mathcal{O}\left(\log\left( \textstyle \sum_i |S_i| \right)\right) = \mathcal{O}(\log(n))</math> होती है जैसा कि साधारण [[तुरंत चयन|क्विकसेलेक्ट]] में होता है। इस प्रकार, कुल मान्य चलने का अपेक्षित समय<math>\mathcal{O}\left(p\log(n/p)\log(n)\right)</math> होता है।
-समानांतर मल्टीवे मर्ज सॉर्ट पर लागू, इस एल्गोरिथम को समानांतर में लागू किया जाना है जैसे कि रैंक के सभी विभाजक तत्व <math display="inline"> i \frac n p</math> के लिए <math>i = 1,.., p</math> साथ-साथ पाये जाते हैं। इन फाड़नेवाला तत्वों का उपयोग तब प्रत्येक अनुक्रम को विभाजित करने के लिए किया जा सकता है <math>p</math> भागों, के समान कुल चलने के समय के साथ <math>\mathcal{O}\left(p\, \log(n/p)\log(n)\right)</math>.
+पैरालल मल्टीवे मर्ज सॉर्ट पर लागू किया गया, इस एल्गोरिदम को पैरालल में आह्वान किया जाना चाहिए जिससे <math display="inline"> i \frac n p</math> के लिए रैंक के सभी स्प्लिटर तत्व समययोग्य रूप से ढूंढ़े जा सकें। इन स्प्लिटर तत्वों का उपयोग करके प्रत्येक सूची को <math>p</math> भागों में विभाजित किया जा सकता है, जिसमें कुल चलने का समय भागों, के समान कुल चलने के समय के साथ <math>\mathcal{O}\left(p\, \log(n/p)\log(n)\right)</math> होता है।
 ==== स्यूडोकोड ====
-नीचे, समानांतर मल्टीवे मर्ज सॉर्ट एल्गोरिथम का पूरा स्यूडोकोड दिया गया है। हम मानते हैं कि बहु-अनुक्रम चयन से पहले और बाद में  बाधा तुल्यकालन है जैसे कि प्रत्येक प्रोसेसर विभाजन तत्वों और अनुक्रम विभाजन को ठीक से निर्धारित कर सकता है।
+नीचे, पैरालल मल्टीवे मर्ज सॉर्ट एल्गोरिदम का पूर्व प्सेडोकोड दिया गया है। हम यह मानते हैं कि बहुसंचारित चयन के पहले और बाद में बैरियर समक्रमण होता है जिससे प्रत्येक प्रोसेसर सही प्रणाली से विभाजन तत्वों और सूची विभाजन का निर्धारण कर सकता है।
   /**
-   * डी: तत्वों की अवर्गीकृत सरणी
+   * 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'''
-      ओ: = नया ऐरे [0, एन] // आउटपुट ऐरे
+      o := '''new''' Array[0, n]                         // the output array
-      for i = 1 to p समानांतर में करें // प्रत्येक प्रोसेसर समानांतर में
+      '''for''' i = 1 '''to''' p '''do in parallel'''                // each processor in parallel
- <nowiki> S_i := d[(i-1) * n/p, i * n/p] // लंबाई का क्रम n/p</nowiki>
+         S_i := d[(i-1) * n/p, i * n/p] 	         // Sequence of length n/p
- सॉर्ट (S_i) // स्थानीय रूप से सॉर्ट करें
+ 	sort(S_i)                                // sort locally
-          समय होनेवाला बनाना
+         '''synch'''
- v_iv:= msSelect([S_1,...,S_p], i * n/p) // वैश्विक रैंक i * n/p के साथ तत्व
+ 	v_i := msSelect([S_1,...,S_p], i * n/p)          // element with global rank i * n/p
-          समय होनेवाला बनाना
+         '''synch'''
- (S_i, 1, ..., S_i, p)i:= अनुक्रम_विभाजन (si, v_1, ..., v_p) // बाद में s_i को विभाजित करें
+ 	(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) // मर्ज करें और आउटपुट ऐरे को असाइन करें
+ 	o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i)  // merge and assign to output array
-      वापसी ओ
+      '''return''' o
 ==== विश्लेषण ====
-सबसे पहले, प्रत्येक प्रोसेसर असाइन किए गए सॉर्ट करता है <math>n/p</math> जटिलता के साथ  छँटाई एल्गोरिथ्म का स्थानीय रूप से उपयोग करने वाले तत्व <math>\mathcal{O}\left( n/p \; \log ( n/p) \right)</math>. उसके बाद, फाड़नेवाला तत्वों की समय पर गणना की जानी चाहिए <math>\mathcal{O}\left(p \,\log(n/p) \log (n) \right)</math>. अंत में, के प्रत्येक समूह <math>p</math> विभाजन को प्रत्येक प्रोसेसर द्वारा चलने वाले समय के साथ समानांतर में विलय करना पड़ता है <math>\mathcal{O}(\log(p)\; n/p  )</math>  अनुक्रमिक मर्ज एल्गोरिथम का उपयोग करना | पी-वे मर्ज एल्गोरिथम। इस प्रकार, समग्र चलने का समय इसके द्वारा दिया जाता है
+प्रथमतः, प्रत्येक प्रोसेसर को सौंपे गए <math>n/p</math> तत्वों को स्थानीय रूप से किसी भी सॉर्टिंग एल्गोरिदम का उपयोग करके सॉर्ट करना होगा जिसका चलने का समय<math>\mathcal{O}\left( n/p \; \log ( n/p) \right)</math> होगा। इसके बाद, स्प्लिटर तत्वों को गणना की जानी चाहिए जिसके लिए समय <math>\mathcal{O}\left(p \,\log(n/p) \log (n) \right)</math>होगा। अंत में, प्रत्येक प्रोसेसर द्वारा परामर्शिक रूप से <math>p</math> तुकड़ों को संयोजित करने के लिए चलने का समय <math>\mathcal{O}(\log(p)\; n/p  )</math> होगा, जिसके लिए क्रमशः <math>p</math> वाले मर्ज एल्गोरिदम का उपयोग किया जाएगा। इस प्रकार, कुल चलने का समय निम्न मान्यता द्वारा दिया जाता है:
-<math>\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)</math>.
+<math>\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)</math> यहाँ प्रत्येक प्रोसेसर की खपत तय करने के लिए प्रायोगिक जरूरतों और सूचनाओं के साथ इस प्रारंभिक नतीजे का अनुकूलन करें।
 ==== व्यावहारिक अनुकूलन और अनुप्रयोग ====
-मल्टीवे मर्ज सॉर्ट एल्गोरिथम अपनी उच्च समांतरता क्षमता के माध्यम से बहुत स्केलेबल है, जो कई प्रोसेसरों के उपयोग की अनुमति देता है। यह एल्गोरिथम को बड़ी मात्रा में डेटा सॉर्ट करने के लिए  व्यवहार्य उम्मीदवार बनाता है, जैसे कि [[कंप्यूटर क्लस्टर]] में संसाधित। इसके अलावा, चूंकि ऐसी प्रणालियों में मेमोरी आमतौर पर सीमित संसाधन नहीं होती है, मर्ज सॉर्ट की अंतरिक्ष जटिलता का नुकसान नगण्य है। हालांकि, ऐसी प्रणालियों में अन्य कारक महत्वपूर्ण हो जाते हैं, जिन्हें समानांतर रैंडम-एक्सेस मशीन पर मॉडलिंग करते समय ध्यान में नहीं रखा जाता है। यहां, निम्नलिखित पहलुओं पर विचार करने की आवश्यकता है: मेमोरी पदानुक्रम, जब डेटा प्रोसेसर कैश में फिट नहीं होता है, या प्रोसेसर के बीच डेटा के आदान-प्रदान का संचार ओवरहेड होता है, जो  अड़चन बन सकता है जब डेटा को साझा किए गए माध्यम से एक्सेस नहीं किया जा सकता है। याद।
+मल्टीवे मर्ज सॉर्ट एल्गोरिदम अपनी उच्च पैराललीकरण क्षमता के माध्यम से बहुत स्केलेबल है, जिससे इसे कई प्रोसेसरों का उपयोग करने की अनुमति मिलती है। यह एल्गोरिदम बड़ी मात्रा में डेटा को सॉर्ट करने के लिए उपयुक्त विकल्प होता है, जैसे कि [[कंप्यूटर क्लस्टर]] में प्रोसेस किए जाने वाले डेटा। इसके अतिरिक्त, चूंकि इस प्रकार के प्रणाली में सामान्यतः मेमोरी सीमित संसाधन नहीं होता है, इसलिए मर्ज सॉर्ट के अतिरिक्त स्थानीयता जटिलता की गणना नहीं की जा सकती है। चूंकि, इस प्रकार के सिस्टमों में अन्य कारक महत्वपूर्ण होते हैं, जो पीआरएएम पर मॉडलिंग करते समय ध्यान में नहीं लिए जाते हैं। यहाँ, निम्नलिखित पहलुओं को विचार में लेने की आवश्यकता होती है: मेमोरी हाइयरार्की, जब डेटा प्रोसेसर कैश में फिट नहीं होती है, या प्रोसेसरों के बीच डेटा आदान-प्रदान की संचालन ओवरहेड, जो जब डेटा साझा मेमोरी के माध्यम से उपलब्ध नहीं हो सकती है, बॉटलनेक बन सकता है।
-[[पीटर सैंडर्स (कंप्यूटर वैज्ञानिक)]] एट अल। अपने पेपर में मल्टीलेवल मल्टीवे मर्जसॉर्ट के लिए  [[थोक तुल्यकालिक समानांतर]] एल्गोरिथम प्रस्तुत किया है, जो विभाजित करता है <math>p</math> प्रोसेसर में <math>r</math> आकार के समूह <math>p'</math>. सभी प्रोसेसर पहले स्थानीय रूप से सॉर्ट करते हैं। सिंगल लेवल मल्टीवे मर्जसॉर्ट के विपरीत, इन अनुक्रमों को तब विभाजित किया जाता है <math>r</math> भागों और उपयुक्त प्रोसेसर समूहों को सौंपा गया। इन चरणों को उन समूहों में पुनरावर्ती रूप से दोहराया जाता है। यह संचार को कम करता है और विशेष रूप से कई छोटे संदेशों के साथ होने वाली समस्याओं से बचाता है। अंतर्निहित वास्तविक नेटवर्क की पदानुक्रमित संरचना का उपयोग प्रोसेसर समूहों (जैसे [[19 इंच का रैक]], कंप्यूटर क्लस्टर, ...) को परिभाषित करने के लिए किया जा सकता है।<ref name=":0" />
+इस प्रकार [[पीटर सैंडर्स (कंप्यूटर वैज्ञानिक)]] एट अल. अपने पेपर में मल्टीलेवल मल्टीवे मर्जसॉर्ट के लिए [[थोक तुल्यकालिक समानांतर]] एल्गोरिथम प्रस्तुत किया है, जो बहुस्तरीय बहुदिशा मर्जसॉर्ट के लिए <math>p</math> प्रोसेसरों को <math>r</math> आकार के समूहों में विभाजित करता है। सभी प्रोसेसर पहले स्थानीय रूप से सॉर्ट करते हैं। एकल स्तर के बहुदिशा मर्जसॉर्ट के विपरीत, इन सरणियों को फिर से <math>r</math> भागों में विभाजित किया जाता है और उचित प्रोसेसर समूहों को सौंपा जाता है। इन कदमों को संघात्मक रूप से पुनरावृत्त किया जाता है। इससे संचार को कम किया जाता है और विशेष रूप से छोटे संदेशों की समस्याओं से बचा जाता है। असली नेटवर्क की पठनीय संरचना का उपयोग प्रोसेसर समूहों को परिभाषित करने के लिए किया जा सकता है (जैसे [[19 इंच का रैक]], कंप्यूटर क्लस्टर, ... आदि होता है। ) <ref name=":0" />
 === आगे के संस्करण ===
-मर्ज सॉर्ट पहले सॉर्टिंग एल्गोरिदम में से  था जहां ओ (1) मर्ज सुनिश्चित करने के लिए रिचर्ड कोल ने  चतुर सबसैंपलिंग एल्गोरिदम का उपयोग करके इष्टतम गति प्राप्त की थी।<ref>{{Cite journal |last1=Cole |first1=Richard |date=August 1988 |title=Parallel merge sort |journal=SIAM J. Comput. |volume=17 |issue=4 |pages=770–785 |citeseerx=10.1.1.464.7118 |doi=10.1137/0217049|s2cid=2416667 }}</ref> अन्य परिष्कृत समानांतर छँटाई एल्गोरिदम कम स्थिरांक के साथ समान या बेहतर समय सीमा प्राप्त कर सकते हैं। उदाहरण के लिए, 1991 में डेविड पॉवर्स ने  समानांतर क्विकसॉर्ट (और  संबंधित [[आपको कामयाबी मिले]]) का वर्णन किया था जो ओ (लॉग एन) समय में [[सीआरसीडब्ल्यू]] समानांतर रैंडम-एक्सेस मशीन (पीआरएएम) पर एन प्रोसेसर के साथ विभाजन को स्पष्ट रूप से निष्पादित करके संचालित कर सकता है।<ref>{{cite book |last=Powers |first=David M. W. |chapter-url=http://citeseer.ist.psu.edu/327487.html |chapter=Parallelized Quicksort and Radixsort with Optimal Speedup |title=Proceedings of International Conference on Parallel Computing Technologies, Novosibirsk |date=1991 |archive-url=https://web.archive.org/web/20070525234405/http://citeseer.ist.psu.edu/327487.html |archive-date=2007-05-25}}</ref> पॉवर्स आगे दिखाता है कि O((log n) पर बैचर के [[बिटोनिक सॉर्टर]] का  पाइपलाइन संस्करण<sup>2</sup>)  तितली [[छँटाई नेटवर्क]] पर समय वास्तव में  PRAM पर उसके O(log n) प्रकार की तुलना में तेज़ है, और वह तुलना, मूलांक और समानांतर छँटाई में छिपे हुए ओवरहेड्स की विस्तृत चर्चा प्रदान करता है।<ref>{{cite conference |last=Powers |first=David M. W. |url= http://david.wardpowers.info/Research/AI/papers/199501-ACAW-PUPC.pdf |title=Parallel Unification: Practical Complexity |conference=Australasian Computer Architecture Workshop Flinders University |date=January 1995}}</ref>
+मर्ज सॉर्ट ऐसा सॉर्टिंग एल्गोरिदम था जिसमें आदर्श गति प्राप्त प्राप्त की थी, जहांरिचर्ड कोल ने ओ (1) मर्ज सुनिश्चित करने के लिए चतुर सबसैम्पलिंग एल्गोरिदम का उपयोग करके इष्टतम गति प्राप्त की थी।<ref>{{Cite journal |last1=Cole |first1=Richard |date=August 1988 |title=Parallel merge sort |journal=SIAM J. Comput. |volume=17 |issue=4 |pages=770–785 |citeseerx=10.1.1.464.7118 |doi=10.1137/0217049|s2cid=2416667 }}</ref> न्य सजग निपणे वाले पैरालल सॉर्टिंग एल्गोरिदम निचेरीत या उससे भी उत्तम समय सीमाओं को कम कॉन्स्टेंट के साथ प्राप्त कर सकते हैं। उदाहरण के लिए, 1991 में डेविड पॉवर्स ने समानांतर क्विकसॉर्ट (और संबंधित [[आपको कामयाबी मिले]]) का वर्णन किया था जो ओ (लॉग एन) समय में [[सीआरसीडब्ल्यू]] समानांतर रैंडम-एक्सेस मशीन (पीआरएएम) पर n प्रोसेसर के साथ O((log n) समय में कार्य कर सकता है, जिसे भाग को निहित करके किया जाता है।<ref>{{cite book |last=Powers |first=David M. W. |chapter-url=http://citeseer.ist.psu.edu/327487.html |chapter=Parallelized Quicksort and Radixsort with Optimal Speedup |title=Proceedings of International Conference on Parallel Computing Technologies, Novosibirsk |date=1991 |archive-url=https://web.archive.org/web/20070525234405/http://citeseer.ist.psu.edu/327487.html |archive-date=2007-05-25}}</ref> पॉवर्स ने यह भी दिखाया है कि [[बिटोनिक सॉर्टर]] के पाइपलाइन रूप O((log n)<sup>2</sup>) समय पर बटरफ्लाई [[छँटाई नेटवर्क|सॉर्टिंग नेटवर्क]] पर समय वास्तव में PRAM पर उसके O(log n) प्रकार की समानता में तेज़ है, और वह समानता, मूलांक और समानांतर सॉर्ट में छिपे हुए ओवरहेड्स की विस्तृत चर्चा प्रदान करता है।<ref>{{cite conference |last=Powers |first=David M. W. |url= http://david.wardpowers.info/Research/AI/papers/199501-ACAW-PUPC.pdf |title=Parallel Unification: Practical Complexity |conference=Australasian Computer Architecture Workshop Flinders University |date=January 1995}}</ref>
-== अन्य प्रकार के एल्गोरिदम के साथ तुलना ==
+== अन्य प्रकार के एल्गोरिदम के साथ समानता ==
-हालाँकि [[ढेर बनाएं और छांटें]] में मर्ज सॉर्ट के समान समय सीमा होती है, इसके लिए मर्ज सॉर्ट के Θ(n) के बजाय केवल Θ(1) सहायक स्थान की आवश्यकता होती है। विशिष्ट आधुनिक आर्किटेक्चर पर, कुशल क्विकॉर्ट कार्यान्वयन आम तौर पर रैम-आधारित सरणियों को सॉर्ट करने के लिए मर्ज सॉर्ट से बेहतर प्रदर्शन करते हैं।{{Citation needed|date=March 2014}} दूसरी ओर, मर्ज सॉर्ट  स्थिर प्रकार है और धीमी-से-पहुंच अनुक्रमिक मीडिया को संभालने में अधिक कुशल है। किसी लिंक की गई सूची को सॉर्ट करने के लिए मर्ज सॉर्ट अक्सर सबसे अच्छा विकल्प होता है: इस स्थिति में मर्ज सॉर्ट को इस तरह लागू करना अपेक्षाकृत आसान होता है कि इसके लिए केवल Θ(1) अतिरिक्त स्थान की आवश्यकता होती है, और लिंक की धीमी रैंडम-एक्सेस प्रदर्शन सूची कुछ अन्य एल्गोरिदम (जैसे कि क्विकसॉर्ट) खराब प्रदर्शन करती है, और अन्य (जैसे हीप्सोर्ट) पूरी तरह से असंभव है।
+हीपसॉर्ट की समय सीमाएं मर्ज सॉर्ट की समान होती हैं, किन्तु यह केवल Θ(1) सहायक स्थान की आवश्यकता होती है चूँकि मर्ज सॉर्ट की Θ(n) की आवश्यकता होती है। प्रामाणिक आधुनिक आर्किटेक्चरों पर, प्रभावी क्विकसॉर्ट के अमलों में सामान्यतः मर्ज सॉर्ट को सुपरियता प्रदान करते हैं जब आरएएम-आधारित एरे को सॉर्ट किया जाता है। दूसरी ओर, मर्ज सॉर्ट स्थिर सॉर्ट होती है और धीरे-धीरे पहुंचने वाले अनुक्रमिक मीडिया को कारगरतापूर्वक संभालने में अधिक कुशल होती है। मर्ज सॉर्ट अधिकांशतः लिंक्ड लिस्ट को सॉर्ट करने के लिए सर्वश्रेष्ठ विकल्प होती है: इस स्थिति में, इसे Θ(1) अतिरिक्त स्थान की आवश्यकता के साथ लागू करना बहुत आसान होता है, और लिंक्ड लिस्ट की धीमी यादृच्छिक पहुंच कार्यक्षमता के कारण कुछ अन्य एल्गोरिदम (जैसे कि क्विकसॉर्ट) कारणों से प्रदर्शन में कमी आती है, और दूसरे (जैसे कि हीपसॉर्ट) पूरी प्रकार से असंभव होते हैं।
-[[पर्ल]] 5.8 के अनुसार, मर्ज सॉर्ट इसका डिफ़ॉल्ट सॉर्टिंग एल्गोरिथम है (यह पर्ल के पिछले संस्करणों में क्विकॉर्ट था)।<ref>{{cite web| url=https://perldoc.perl.org/5.8.8/sort.html| title=Sort – Perl 5 version 8.8 documentation| access-date=2020-08-23}}</ref> [[जावा मंच]] में, [https://docs.oracle.com/javase/9/docs/api/java/util/Arrays.html#sort-java.lang.Object:A- Arrays.sort()] तरीके इस्तेमाल करते हैं मर्ज सॉर्ट या ट्यून्ड क्विकॉर्ट डेटाटाइप के आधार पर और कार्यान्वयन दक्षता के लिए इंसर्शन सॉर्ट पर स्विच करें जब सात से कम सरणी तत्वों को सॉर्ट किया जा रहा हो।<ref>{{cite web |url= https://hg.openjdk.java.net/jdk/jdk/file/9c3fe09f69bc/src/java.base/share/classes/java/util/Arrays.java#l1331 |work=OpenJDK |author=coleenp |date=22 Feb 2019 |title=src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc}}</ref> [[लिनक्स]] कर्नेल अपनी लिंक्ड सूचियों के लिए मर्ज सॉर्ट का उपयोग करता है।<ref>[https://github.com/torvalds/linux/blob/master/lib/list_sort.c linux kernel /lib/list_sort.c]</ref> पायथन (प्रोग्रामिंग लैंग्वेज) टिम्सोर्ट का उपयोग करता है, मर्ज सॉर्ट और इंसर्शन सॉर्ट का  और ट्यूनेड हाइब्रिड, जो [[जावा 7]] में मानक सॉर्ट एल्गोरिथ्म बन गया है (गैर-आदिम प्रकार के सरणियों के लिए),<ref>{{cite web
+[[पर्ल]] 5.8 के रूप में, मर्ज सॉर्ट इसका डिफ़ॉल्ट सॉर्टिंग एल्गोरिथम है (यह पर्ल के पूर्व संस्करणों में क्विकॉर्ट था)।<ref>{{cite web| url=https://perldoc.perl.org/5.8.8/sort.html| title=Sort – Perl 5 version 8.8 documentation| access-date=2020-08-23}}</ref> इस प्रकार [[जावा मंच|जावा प्लेटफार्म]] में, [https://docs.oracle.com/javase/9/docs/api/java/util/Arrays.html#sort-java.lang.Object:A- Arrays.sort()] विधियाँ मर्ज सॉर्ट या ट्यून्ड क्विकसॉर्ट का उपयोग करती हैं आपके डेटाटाइप पर और कार्यान्वयन क्षमता के लिए, जब किसी एरे के सात से कम तत्वों को सॉर्ट किया जा रहा हो तो इन्सर्शन सॉर्ट में स्विच करती हैं।<ref>{{cite web |url= https://hg.openjdk.java.net/jdk/jdk/file/9c3fe09f69bc/src/java.base/share/classes/java/util/Arrays.java#l1331 |work=OpenJDK |author=coleenp |date=22 Feb 2019 |title=src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc}}</ref> इस प्रकार [[लिनक्स]] कर्नेल अपनी लिंक्ड सूचियों के लिए मर्ज सॉर्ट का उपयोग करता है।<ref>[https://github.com/torvalds/linux/blob/master/lib/list_sort.c linux kernel /lib/list_sort.c]</ref> पायथन (प्रोग्रामिंग लैंग्वेज) टिम्सोर्ट का उपयोग करता है, मर्ज सॉर्ट और इंसर्शन सॉर्ट का और ट्यूनेड हाइब्रिड, जो [[जावा 7]] में मानक सॉर्ट एल्गोरिथ्म बन गया है (गैर-आदिम प्रकार के सरणियों के लिए),<ref>{{cite web
   |title       = Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort
   |url         = http://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/bfd7abda8f79
@@ Line 417: / Line 400: @@
   |archive-url  = https://web.archive.org/web/20180126184957/http://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/bfd7abda8f79
   |archive-date = 2018-01-26
-}}</ref> [[Android (ऑपरेटिंग सिस्टम)]] पर,<ref>{{cite web|title=Class: java.util.TimSort<T> |url=https://android.googlesource.com/platform/libcore/+/jb-mr2-release/luni/src/main/java/java/util/TimSort.java |work=Android JDK Documentation |access-date=19 Jan 2015 |url-status=dead |archive-url=https://web.archive.org/web/20150120063131/https://android.googlesource.com/platform/libcore/%2B/jb-mr2-release/luni/src/main/java/java/util/TimSort.java |archive-date=January 20, 2015 }}</ref> और [[जीएनयू ऑक्टेव]] में।<ref>{{cite web
+}}</ref> [[Android (ऑपरेटिंग सिस्टम)|एंड्राइड(ऑपरेटिंग प्रणाली)]] पर,<ref>{{cite web|title=Class: java.util.TimSort<T> |url=https://android.googlesource.com/platform/libcore/+/jb-mr2-release/luni/src/main/java/java/util/TimSort.java |work=Android JDK Documentation |access-date=19 Jan 2015 |url-status=dead |archive-url=https://web.archive.org/web/20150120063131/https://android.googlesource.com/platform/libcore/%2B/jb-mr2-release/luni/src/main/java/java/util/TimSort.java |archive-date=January 20, 2015 }}</ref> और [[जीएनयू ऑक्टेव]] में मानक सॉर्ट एल्गोरिदम बन गया है।<ref>{{cite web
 | title = liboctave/util/oct-sort.cc
 | url = http://hg.savannah.gnu.org/hgweb/octave/file/0486a29d780f/liboctave/util/oct-sort.cc
@@ Line 425: / Line 408: @@
 | at = Lines 23-25 of the initial comment block.
 }}</ref>
 ==टिप्पणियाँ==
 {{reflist|30em}}
@@ Line 515: / Line 496: @@
 * [http://opendatastructures.org/versions/edition-0.1e/ods-java/11_1_Comparison_Based_Sorti.html#SECTION001411000000000000000 Open Data Structures - Section 11.1.1 - Merge Sort], [[Pat Morin]]
-{{DEFAULTSORT:Merge sort}}[[Category: छँटाई एल्गोरिदम]] [[Category: तुलना प्रकार]] [[Category: स्थिर प्रकार]] [[Category: स्यूडोकोड के उदाहरण वाले लेख]] [[Category: फूट डालो और जीतो एल्गोरिदम]]
+{{DEFAULTSORT:Merge sort}}
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Merge sort]]
-[[Category:Created On 08/02/2023]]
+[[Category:Created On 08/02/2023|Merge sort]]
+[[Category:Lua-based templates|Merge sort]]
+[[Category:Machine Translated Page|Merge sort]]
+[[Category:Pages with script errors|Merge sort]]
+[[Category:Templates Vigyan Ready|Merge sort]]
+[[Category:Templates that add a tracking category|Merge sort]]
+[[Category:Templates that generate short descriptions|Merge sort]]
+[[Category:Templates using TemplateData|Merge sort]]
+[[Category:Webarchive template wayback links|Merge sort]]
+[[Category:छँटाई एल्गोरिदम|Merge sort]]
+[[Category:तुलना प्रकार|Merge sort]]
+[[Category:फूट डालो और जीतो एल्गोरिदम|Merge sort]]
+[[Category:स्थिर प्रकार|Merge sort]]
+[[Category:स्यूडोकोड के उदाहरण वाले लेख|Merge sort]]

Anonymous

Search

मर्ज़ सॉर्ट: Difference between revisions

Latest revision as of 10:59, 27 July 2023

एल्गोरिथम

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

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

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

सूचियों का उपयोग करके बॉटम -उप कार्यान्वयन

विश्लेषण

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

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

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

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

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

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

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

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

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

मूल विचार

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

स्यूडोकोड

विश्लेषण

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

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

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

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories