導(dǎo)語

歸并排序，顧名思義，先遞歸分解數(shù)列，再進行合并，是分治策略非常典型的應(yīng)用。假設(shè)初始序列含有 n 個元素，則可看做是n個有序的子序列，每個子序列的長度為1， 然后兩兩合并，得到 n/2 個長度為 2 或為 1 的子序列；再兩兩合并,……,如此重復(fù)，直至得到一個長度為 n 的有序序列為止。

歸并排序的核心思想是將兩個有序序列合并為一個序列，代碼如下：

void mergeArray(int *array, int first, int middle, int last) {
    int length = last - first + 1;
    int temp[length], i = first, j = middle + 1, k = 0;
    while (i <= middle && j <= last) {
        if(array[i] >= array[j]) {
            temp[k++] = array[j++];
        } else {
            temp[k++] = array[i++];
        }
    }
    
    while (i <= middle) {
        temp[k++] = array[i++];
    }
    
    while (j <= last) {
        temp[k++] = array[j++];
    }
    k = 0;
    for (int t = first; t <= last; t++, k++) {
        array[t] = temp[k];
    }
}

接下來遞歸調(diào)用：

void mergeSort(int *a, int first, int last) {
    if (first < last) {
        int middle = (first + last) / 2;
        mergeSort(a, first, middle);
        mergeSort(a, middle + 1, last);
        mergeArray(a, first, middle, last);
    }
}