归并排序

导语

归并排序，顾名思义，先递归分解数列，再进行合并，是分治策略非常典型的应用。假设初始序列含有 n 个元素，则可看做是n个有序的子序列，每个子序列的长度为1， 然后两两合并，得到 n/2 个长度为 2 或为 1 的子序列；再两两合并,……,如此重复，直至得到一个长度为 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];
    }
}

接下来递归调用：

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);
    }
}