思想

歸併排序（merge sort）是建立在歸併操作上的一種有效的排序演算法,它以 O(nlogn) 最壞情形運行時間運行。它是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列：即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。歸併排序可並行實現。

歸併排序示例圖如下：

實現

合併操作

基本的合併演算法是取兩個輸入數組 A 和 B、一個輸出數組 C，以及三個計數器 Aptr， Bptr， Cptr。它們初始置於對應數組的開始端。A[Aptr]和 B[Bptr]中的較小者被拷貝到 C 中的下一個位置，相關的計數器向前推進一步。當兩個輸入表有一個用完時，則將另一個表中剩餘部分拷貝到 C 中。

如果對 Merge 的每個遞歸調用均局部聲明一個臨時數組，那麼在任一時刻就可能有 log N 個臨時數組處在活動期，這對於小記憶體機器是致命的。另一方面，如果 Merge 常式動態分配並釋放最小量臨時記憶體，那麼由 malloc 占用的時間會很多。因此，可將輸入數組分成兩個輸入數組。

/**
*    @description 對數組a的 a[leftPos, rightPos - 1] 和 a[rightPos, rightEnd] 兩部分進行合併操作，結果暫存到tmpArray中，最後拷貝回數組a。
*/
void Merge(ElementType a[], ElementType tmpArray[], int leftPos, int rightPos, int rightEnd)
{
    int i, leftEnd, numOfElements, tmpPos;
 
    leftEnd = rightPos - 1;
    tmpPos = leftPos;
    numOfElements = rightEnd - leftPos + 1;       
 
    //main loop
    while (leftPos <= leftEnd && rightPos <= rightEnd)
        if (a[leftPos] < a[rightPos])
            tmpArray[tmpPos++] = a[leftPos++];
        else
            tmpArray[tmpPos++] = a[rightPos++];
 
    //get rest of first half
    while (leftPos <= leftEnd)
        tmpArray[tmpPos++] = a[leftPos++];
 
    //get rest of second half
    while (rightPos <= rightEnd)
        tmpArray[tmpPos++] = a[rightPos++];
 
    //copy tmpArray back
    for (i = 0; i < numOfElements; ++i, rightEnd--)
        a[rightEnd] = tmpArray[rightEnd];
}

歸併排序

/**
*    @description 歸併排序主演算法，對數組a[left, right] 進行歸併排序，使用到了暫存數組tmpArray。
*/
void MSort(ElementType a[], ElementType tmpArray[], int left, int right)
{
    int center;
 
    if (left < right)
    {
        center = (left + right) / 2;
        MSort(a, tmpArray, left, center);
        MSort(a, tmpArray, center + 1, right);
        Merge(a, tmpArray, left, center + 1, right);
    }
}

演算法主體

/**
*    @description 歸併排序演算法，封裝了開闢臨時存儲空間的操作。
*/
void MergeSort(ElementType a[], int n)
{
    ElementType *tmpArray;
 
    tmpArray = (ElementType *)malloc(sizeof(ElementType) * n);
    if (tmpArray != NULL)
    {
        MSort(a, tmpArray, 0, n - 1);
        free(tmpArray);
    }
    else
        puts("No space of tmp Array!");
}