原理解释

分治排序的原理很简单，运用分治的思想，先将左边部分的数组排序，再将右边部分的数组排序，再按大小归并

递归执行，直到二分至左右数组只含有一个数，此时视为左右数组已经排序完成，之间按照大小归并，在弹栈，完成递归，排序结束

实现

merge 归并实现

这里需要将左右数组中的元素按照大小合并成一个有序数组，引入两个指针，比较二者指向的元素的大小，将较小的数放进辅助数组(以升序为例)，同时该数指针向后移动一位，直到一个数组的元素全部放进辅助数组中，再将另外一个数组的元素直接放进辅助数组

最后将辅助数组中的元素放进原数组对应的位置

给出代码：

void merge(int l, int m, int r) {  // l ~ m 和 m+1 ~ r 右侧
    int a = L;
    int b = m + 1;
    int index = l;
    while (a <= m && b <= r)
        help[index++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];

    // 左侧指针，右侧指针，必有一个越界，一个不越界
    while (a <= m)
        help[index++] = arr[a++];

    while (b <= r)
        help[index++] = arr[b++];

    for (int i = l; i <= r; i++)
        arr[i] = help[i];
}

递归实现

递归实现很简单，注意结束条件是区间内只剩下一个元素

代码：

void mergeSort1(int l, int r) {  // 在 r ~ l下标范围内排序 递归
    if (l == r)
        return;
    int m = (l + r) >> 1;  // /2的位运算写法
    mergeSort1(l, m);
    mergeSort1(m + 1, r);
    merge(l, m, r);
}

实际中使用递归实现较多

非递归实现

枚举步长划分区间，归并子区间，速度比递归实现快一点，但是实际中灵活性差一点，仅作了解

void mergeSort2() {                   // 非递归实现
    for (int i = 1; i < n; i *= 2) {  // 枚举步长
        int l = 0, m, r;
        // 内部分组
        while (l < n) {
            m = l + i - 1;
            if (m + 1 > n - 1)
                // 无右侧
                break;
            r = min(l + (i << 1) - 1, n - 1);
            merge(l, m, r);
            l = r = 1;
        }
    }
}