归并排序

归并排序基于分治思想，

(1)选择中间坐标m = (l+r)/2，将序列划分为[l, m]和[m+1, r]两部分；

(2)递归处理左半序列和右半序列；

(3)归并两个子序列，使归并后的全序列有序。

void MergeSort(int a[], int l, int r) {
    if (l >= r) return;

    int m = (l+r)/2;

    MergeSort(a, l, m);
    MergeSort(a, m+1, r);

    int k = 0, i = l, j = m+1;
    while (i <= m && j <= r)
        if (a[i] <= a[j]) t[k++] = a[i++];
        else t[k++] = a[j++];
    while (i <= m) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];

    for (i = l, k = 0; i <= r; i++, k++) a[i] = t[k];
}

注解：

(1)也可选择中间坐标m = (l+r+1)/2，将序列划分为[l, m-1]和[m, r]两部分：

void MergeSort(int a[], int l, int r) {
    if (l >= r) return;

    int m = (l+r+1)/2;

    MergeSort(a, l, m-1);
    MergeSort(a, m, r);

    int k = 0, i = l, j = m;
    while (i <= m-1 && j <= r)
        if (a[i] <= a[j]) t[k++] = a[i++];
        else t[k++] = a[j++];
    while (i <= m-1) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];

    for (i = l, k = 0; i <= r; i++, k++) a[i] = t[k];
}

---