上《算法分析与设计》这门课的时候老师提到了归并排序，并要求写出三路、四路的归并排序算法。

那好吧，正好从头复习一下归并排序

什么是归并排序

简单来说，就是把两个已经有序的子序列合并为一个有序序列。

需要注意的是，“归并”的“归”指的并不是递归，而是带有合并的意思。

直接上代码

假定有一个序列

arr = {3, 4, 6, 7, 1, 2, 5, 8};

注意观察，可以将这个序列的前半部分和后半部分分别看作两个已经是有序的子序列

subArr1 = {3, 4, 6, 7};
subArr2 = {1, 2, 5, 8};

我们对 arr 数组进行归并排序

在这里面我们需要三个指针：

• left：当前序列的第一个元素下标
• right：当前序列的最后一个元素的下标
• mid：当前序列中位元素的下标

再利用两个index索引作为循环的依据

*注意！在定义索引时，因为 j 的位置位于 mid 的下一个位置，所以应该先定义 mid ， 再定义 j *

vector<int> merge(vector<int> &arr, int left, int right) {

    int i = left;
    int mid = (left + right) / 2;
    int j = mid + 1;

    vector<int> temp(right - left + 1);
    int cur = 0;
    while ( i <= mid && j <= right ) {
        temp[cur++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }

    // 查看是否有一个子序列已经全部添加到temp数组中，而另一个子序列还有剩余的情况
    while ( i <= mid ) {
        temp[cur++] = arr[i++];
    }
    while ( j <= right ) {
        temp[cur++] = arr[j++];
    }

    for ( int i = 0; i < temp.size(); i++ ) {
        arr[left + i] = temp[i];
    }

    return arr;

}

但这样写显然是不正确的，因为它只对当前的示例(一个序列可视为由两个有序子序列构成)

那咋办嘛

让程序递归调用一下就好了

//递归调用先对左右子数组进行排序
merge(arr, left, mid);
merge(arr, mid+1, right);

完成版(二路归并)

vector<int> merge(vector<int> &arr, int left, int right) {
    // 加个判断
    if ( left >= right ) return arr;

    int mid = (left + right) / 2;
    merge(arr, left, mid);
    merge(arr, mid+1, right);

    int i = left;
    int j = mid + 1;

    vector<int> temp(right - left + 1);
    int cur = 0;
    while ( i <= mid && j <= right ) {
        temp[cur++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }

    while ( i <= mid ) {
        temp[cur++] = arr[i++];
    }
    while ( j <= right ) {
        temp[cur++] = arr[j++];
    }

    for ( int i = 0; i < temp.size(); i++ ) {
        arr[left + i] = temp[i];
    }

    return arr;

}

三路、四路待更新