मर्ज सॉर्ट

कंप्यूटर विज्ञान में, मर्ज सॉर्ट, जिसको आमतौर पर मर्जसॉर्ट बोला जाता है, एक कुशल, सामान्य प्रयोजन, तुलना-आधारित सॉर्टिंग एल्गोरिथ्म है। अधिकांश कार्यान्वयन एक स्थिर सॉर्ट का उत्पादन करते हैं, जिसका अर्थ है कि समान तत्वों का क्रम इनपुट और आउटपुट में समान है। मर्ज सॉर्ट एक विभाजित और विजेता एल्गोरिथ्म है जिसका आविष्कार जॉन वाॅन न्यूमन ने १९४५ में किया था। गोल्डस्टाइन और वॉन न्यूमैन की १९४८ की शुरुआत में एक रिपोर्ट में बॉटम-अप मर्जोर्ट का विस्तृत विवरण और विश्लेषण दिखाई दिया।

एल्गोरिथ्म

वैचारिक रूप से, एक मर्ज सॉर्ट इस प्रकार काम करता है:

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

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

उदाहरण के लिए टोप-डाउन मर्ज सॉर्ट एल्गोरिथ्म का कोड सी जैसी प्रोग्रामिंग भाषा में, जो पुन: सूची को सब्लिस्ट में विभाजित करता है (जिनको रन्स बोला गया है इस उदाहरण मे) जब तक सब्लिस्ट मे एक से ज़्यादा तत्त्व है।फिर उन सब्लिस्ट को मर्ज करके क्रमबद्ध सूची प्राप्त करी जाती है।इसे समझने में मदद करने के लिए, हम २ तत्वों के साथ एक सूची पर विचार करते है।तत्वों को 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(B, 0, n, A);   // sort data from B[] into A[]
}

// Sort the given run of array A[] using array B[] as a source.
// 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(A[], iBegin, iMiddle, iEnd, B[])
{
    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)) किया जाता है।

बौटम-अप कार्यान्वयन

उदाहरण के लिए बौटम-अप मर्ज सॉर्ट एल्गोरिथ्म का कोड सी जैसी प्रोग्रामिंग भाषा में, जो सूची को 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 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 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];
}

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

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

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)

टूर्नामेंट रिप्लेसमेंट चयन प्रकार का उपयोग बाहरी सॉर्टिंग एल्गोरिदम के लिए प्रारंभिक रन इकट्ठा करने के लिए किया जाता है।

विश्लेषण

n ऑब्जेक्ट्स को सॉर्ट करने में, मर्ज सॉर्ट में O(n log n) का औसत और सबसे खराब प्रदर्शन होता है। यदि लंबाई n की सूची के लिए मर्ज के प्रकार का रनिंग टाइम T(n) है, तो पुनरावर्तन T(n) = 2T(n/2) + n एल्गोरिथम की परिभाषा से अनुसरण करता है (एल्गोरिथ्म को दो सूचियों पर लागू करें जिनकी लम्बाई मूल सूची की आधी हो, और परिणामी दो सूचियों को मिलाने के लिए उठाए गए n चरणों को जोड़ें)।बंद रूप फॉर्म मास्टर प्रमेय से विभाजन और जीत की पुनरावृत्ति के लिए अनुसरण करता है।

सबसे खराब स्थिति में, मर्ज सॉर्ट मे तुलना की संख्या सॉर्टिंग संख्याओं द्वारा दी जाती है। ये संख्या (n ⌈lg n⌉ − 2^⌈lg n⌉ + 1) के बराबर या उससे छोटी होती है, जो कि (n lg n − n + 1) और (n lg n + n + O(lg n)) के बीच है।

बड़े n और बेतरतीब ढंग से ऑर्डर की गई इनपुट सूची के लिए, मर्ज की तरह की अपेक्षित (औसत) तुलनाओं की संख्या α · n सबसे खराब स्थिति की तुलना में कम है, जहां <math>\alpha = -1 + \sum_{k=0}^\infty \frac1{2^k+1} \approx 0.2645</math>।

सबसे खराब स्थिति में, मर्ज सॉर्ट औसत मामले में क्विकसॉर्ट की तुलना में लगभग ३९% कम तुलना करता है। चालों के संदर्भ में, मर्ज सॉर्ट की सबसे खराब स्थिति जटिलता हे (n लॉग एन) - क्विकसॉर्ट के सर्वश्रेष्ठ मामले के रूप में एक ही जटिलता है, और मर्ज सॉर्ट का सबसे अच्छा मामला सबसे खराब मामले के रूप में कई पुनरावृत्तियों के बारे में आधा लेता है।

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

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