导语
归并排序，顾名思义，先递归分解数列，再进行合并，是分治策略非常典型的应用。假设初始序列含有 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);
}
}
