// Massiv A[] nizamlanmalıdır; massiv B[] işçi massivdir.
TopDownMergeSort(A[], B[], n)
{
    CopyArray(A, 0, n, B);           // A[] massivini B[]massivinə kopyala
    TopDownSplitMerge(B, 0, n, A);   // elementləri B[] massivindən A[] massivinə nizamla
}

// iBegin massivə daxildir; iEnd isə daxil deyil (A[iEnd] çoxluğa daxil deyil).
TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
    if(iEnd - iBegin < 2)                       // əgər size == 1
        return;                                 // bunu nizamlanmış fərz et
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = orta nöqtə
    // rekursiv olaraq hər iki siyahını A[] massivindən B[] massivinə nizamla
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sol siyahını nizamla
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sağ siyahını nizamla
    // nəticədə alınan siyahıları B[]massivindən A[] massivinə birləşdir
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

//  Sol siyahı A[ iBegin:iMiddle-1].
// Sağ siyahı A[iMiddle:iEnd-1   ].
// Nəticə B[ iBegin:iEnd-1   ].
TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
    i = iBegin, j = iMiddle;
    
    // Sol və ya sağ siyahılarda element olduqca...
    for (k = iBegin; k < iEnd; k++) {
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;    
        }
    } 
}

CopyArray(A[], iBegin, iEnd, B[])
{
    for(k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

// massiv A[] nizamlanmalıdır, massiv B[] işçi massivdir.
void BottomUpMergeSort(A[], B[], n)
{
    for (width = 1; width < n; width = 2 * width)
    {
        for (i = 0; i < n; i = i + 2 * width)
        {
            // İki siyahını birləşdir: 
            //A[i:i+width-1] və A[i+width:i+2*width-1]: B[] massivinə
            // və ya A[i:n-1]-i B[] massivinə kopyala  ( if(i+width >= n) )

            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
        // B massivi uzunluğu 2*width olan siyahılardan ibarətdir 
        // Növbəti iterasiya üçün B massivini A massivinə kopyala.
        // Daha səmərəli implementasiya A və B massivlərinin rolunu dəyişmək olar 
        CopyArray(B, A, n);
        // indi A massivi uzunluğu 2*width olan siyahılarldan ibarədir  
    }
}

// Sol siyahı A[iLeft :iRight-1].
// Sağ siyahı A[iRight:iEnd-1  ].
BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    // Sol və ya sağ siyahılarda element olduqca...
    for (k = iLeft; k < iEnd; k++) {
       
        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];
}