歸並排序算法原理分析與代碼實現

  歸並排序是建立在歸並操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用，歸並排序將兩個已排序的表合並成一個表。
   

歸並排序基本原理

通過對若干個有序結點序列的歸並來實現排序。

所謂歸並是指將若干個已排好序的部分合並成一個有序的部分。

歸並排序基本思想

設兩個有序的子序列(相當於輸入序列)放在同一序列中相鄰的位置上：array[low..m]，array[m + 1..high]，先將它們合並到一個局部的暫存序列 temp (相當於輸出序列)中，待合並完成後將 temp 復制回 array[low..high]中，從而完成排序。

在具體的合並過程中，設置 i，j 和 p 三個指針，其初值分別指向這三個記錄區的起始位置。合並時依次比較 array[i] 和 array[j] 的關鍵字，取關鍵字較小（或較大）的記錄復制到 temp[p] 中，然後將被復制記錄的指針 i 或 j 加 1，以及指向復制位置的指針 p加 1。重復這一過程直至兩個輸入的子序列有一個已全部復制完畢(不妨稱其為空)，此時將另一非空的子序列中剩余記錄依次復制到 array 中即可。

若將兩個有序表合並成一個有序表，稱為2-路歸並。

舉例說明"歸並排序的排序過程"

看下面歸並排序的兩種排序過程

 1.待排序列(14,12,15,13,11,16)

假設我們有一個沒有排好序的序列，那麼首先我們使用分割的辦法將這個序列分割成一個個已經排好序的子序列。然後再利用歸並的方法將一個個的子序列合並成排序好的序列。分割和歸並的過程可以看下面的圖例。

                  先"分割"再"合並"

從上圖可以看出，我們首先把一個未排序的序列從中間分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一個一個的數據，再把這些數據兩兩歸並到一起，使之有序，不停的歸並，最後成為一個排好序的序列。

2.待排序列(25,57,48,37,12,92,86)

歸並排序實現源碼：
static Ret merge_sort_impl(void** storage, void** array, size_t low, size_t mid, size_t high, DataCompareFunc cmp)
{
    size_t i = low;
    size_t j = low;
    size_t k = mid;

    if((low + 1) < mid)
    {
        size_t x = low + ((mid - low) >> 1);
        merge_sort_impl(storage, array, low, x, mid, cmp);
    }
   
    if((mid + 1) < high)
    {
        size_t x = mid + ((high - mid) >> 1);
        merge_sort_impl(storage, array, mid, x, high, cmp);
    }

   
    while(j < mid && k < high)
    {
        if(cmp(array[j], array[k]) <= 0)
        {
            storage[i++] = array[j++];
        }
        else
        {
            storage[i++] = array[k++];
        }
    }

    while(j < mid)
    {
        storage[i++] = array[j++];
    }

    while(k < high)
    {
        storage[i++] = array[k++];
    }

    for(i = low; i < high; i++)
    {
        array[i] = storage[i];
    }

    return RET_OK;
}