ಮರ್ಜ್ ಸಾರ್ಟ್ (ವಿಲೀನ ವಿಂಗಡಣೆ)

ಮರ್ಜ್ ಸಾರ್ಟ್

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.
ಕ್ಲಾಸ್	{{{class}}}
ಡೇಟಾ ರಚನೆ	{{{data}}}
ಪ್ರತಿಕೂಲ ಸ್ಥಿತಿ ವಿಶ್ಲೇಷಣೆ	{{{time}}}
ಕೆಟ್ಟ-ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆ	{{{space}}}

ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಮರ್ಜ್ ಸಾರ್ಟ್ (ಸಾಮಾನ್ಯವಾಗಿ ವಿಲೀನಗೊಳಿಸುವಿಕೆ ಎಂದು ಸಹ ಉಚ್ಚರಿಸಲಾಗುತ್ತದೆ) ಒಂದು ಸಮರ್ಥ, ಸಾಮಾನ್ಯ-ಉದ್ದೇಶ ಮತ್ತು ಹೋಲಿಕೆ-ಆಧಾರಿತ ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಹೆಚ್ಚಿನ ಅನುಷ್ಠಾನಗಳು ಸ್ಥಿರವಾದ ವಿಂಗಡಣೆ (ಸ್ಟೇಬಲ್ ಸಾರ್ಟ್) ಯನ್ನು ಉತ್ಪಾದಿಸುತ್ತವೆ. ಅಂದರೆ ಸಮಾನ ಎಲಿಮೆಂಟ್ ಗಳ ಸಾಪೇಕ್ಷ ಕ್ರಮವು ಇನ್‌ಪುಟ್ ಮತ್ತು ಔಟ್‌ಪುಟ್‌ನಲ್ಲಿ ಒಂದೇ ಆಗಿರುತ್ತದೆ. ವಿಲೀನ ವಿಂಗಡಣೆಯು ವಿಭಜಿತ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವ (ಡಿವೈಡ್ ಅಂಡ್ ಕಾನ್ಕರ್) ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಇದನ್ನು 1945 ರಲ್ಲಿ ಜಾನ್ ವಾನ್ ನ್ಯೂಮನ್ ಕಂಡುಹಿಡಿದನು 1948 ರ ಹಿಂದೆಯೇ ಗೋಲ್ಡ್‌ಸ್ಟೈನ್ ಮತ್ತು ವಾನ್ ನ್ಯೂಮನ್‌ರ ವರದಿಯಲ್ಲಿ ಬಾಟಮ್-ಅಪ್ ವಿಲೀನ ರೀತಿಯ ವಿವರವಾದ ವಿವರಣೆ ಮತ್ತು ವಿಶ್ಲೇಷಣೆ ಕಾಣಿಸಿಕೊಂಡಿತು

ಅಲ್ಗಾರಿದಮ್

ಕಲ್ಪನಾತ್ಮಕವಾಗಿ, ಮರ್ಜ್ ಸಾರ್ಟ್ ಈ ಕೆಳಗಿನಂತೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ:

1. ವಿಂಗಡಿಸದ ಅರ್ರೆಯನ್ನು n ಸಬ್ ಅರ್ರೆ ಗಳಾಗಿ ವಿಂಗಡಿಸಿ, ಪ್ರತಿಯೊಂದೂ ಒಂದು ಎಲಿಮೆಂಟನ್ನು ಹೊಂದಿರುತ್ತದೆ (ಒಂದು ಎಲಿಮೆಂಟಿನ ಅರ್ರೆಯನ್ನು ವಿಂಗಡಿಸಲಾಗಿದೆ ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ).
2. ಒಂದೇ ಒಂದು ಸಬ್ ಅರ್ರೆಯನ್ನು ಉಳಿದಿರುವವರೆಗೆ ಹೊಸ ವಿಂಗಡಿಸಲಾದ ಸಬ್ ಅರ್ರೆಗಳನ್ನು ಉತ್ಪಾದಿಸಲು ಸಬ್ ಅರ್ರೆಗಳನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ವಿಲೀನಗೊಳಿಸಿ . ಇದು ವಿಂಗಡಿಸಲಾದ ಅರ್ರೆಯಾಗಿರುತ್ತದೆ.

ಟಾಪ್-ಡೌನ್ ಅನುಷ್ಠಾನ

// 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];
}

ಸಂಪೂರ್ಣ ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸುವ ಮೂಲಕ ಸಾಧಿಸಲಾಗುತ್ತದೆ  .