归并排序是一种采用分治策略的简单高效排序算法，最好和最坏时间复杂度均为O(nlogn)，优势在于它稳定、适用于外排序，缺点在于需要额外的O(n)辅助空间。
排序思路
- 将待排序区间分成左右两块大小相同的区间
- 分别对左右两子区间排序
- 归并左右子区间使整体区间有序
上述做法用递归很容易实现，递归出口是区间只有1个元素，无需再分。
以下是对整型数组按从小到大排列的示例代码。
void Merge(int *a, int lbeg, int rbeg, int rend, int *t) {
int i = lbeg, j = rbeg, k = lbeg;
while (i < rbeg && j < rend)
t[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i < rbeg) t[k++] = a[i++];
while (j < rend) t[k++] = a[j++];
for (i = lbeg; i < rend; i++)
a[i] = t[i];
}
void MSort(int *a, int lbeg, int rend, int *t) {
if (lbeg + 1 < rend) {
int rbeg = (lbeg + rend) / 2;
MSort(a, lbeg, rbeg, t);
MSort(a, rbeg, rend, t);
Merge(a, lbeg, rbeg, rend, t);
}
}
void MergeSort(int *a, int size) {
int *t = malloc(sizeof(int) * size);
MSort(a, 0, size, t);
free(t);
}
自下而上观察归并排序的过程，可以写出对应的非递归做法。
void MergeSort(int *a, int size) {
int i, j, *t = malloc(sizeof(int) * size);
for (i = 1; i < size; i *= 2)
for (j = 0; j + i < size; j += 2 * i)
Merge(a, j, j + i, min(size, j + 2 * i), t);
free(t);
}
