将两个有序数组合并为一个有序数组

在第二个列表向第一个列表逐个插入的过程中，由于第二个列表已经有序，所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中，每次插入时，只需要从上次插入的位置开始，继续向后寻找插入位置即可。这样一来，我们最多只需要将两个有序数组遍历一次就可以完成合并。

vector<int> merge(vector<int> arr1, vector<int> arr2)
{vector<int> result;int index1 = 0, index2 = 0;while (index1 < arr1.size() && index2 < arr2.size()) {if (arr1[index1] <= arr2[index2]) {result[index1 + index2] = arr1[index1];index1++;}else {result[index1 + index2] = arr2[index2];index2++;}}// 将剩余数字补到结果数组之后while (index1 < arr1.size()) {result[index1 + index2] = arr1[index1];index1++;}while (index2 < arr2.size()) {result[index1 + index2] = arr2[index2];index2++;}return result;
}

将两个无序数组合并为一个有序数组

我们可以把数组不断地拆成两份，直到只剩下一个数字时，这一个数字组成的数组我们就可以认为它是有序的。然后通过上述合并有序列表的思路，将 1 个数字组成的有序数组合并成一个包含 2 个数字的有序数组，再将 2 个数字组成的有序数组合并成包含 4 个数字的有序数组…直到整个数组排序完成。

 void mergeSort(vector<int> arr) {if (arr.size() == 0) return;vector<int> result = mergeSort(arr, 0, arr.size() - 1);// 将结果拷贝到 arr 数组中for (int i = 0; i < result.size(); i++) {arr[i] = result[i];}
}// 对 arr 的 [start, end] 区间归并排序vector<int> mergeSort(vector<int> arr, int start, int end) {// 只剩下一个数字，停止拆分，返回单个数字组成的数组if (start == end) return vector<int>{arr[start]};int middle = (start + end) / 2;// 拆分左边区域vector<int> left = mergeSort(arr, start, middle);// 拆分右边区域vector<int> right = mergeSort(arr, middle + 1, end);// 合并左右区域return merge(left, right);
}

归并排序的优化：减少临时空间的开辟

为了减少在递归过程中不断开辟空间的问题，我们可以在归并排序之前，先开辟出一个临时空间，在递归过程中统一使用此空间进行归并即可。

// 将 result 的 [start, middle] 和 [middle + 1, end] 区间合并
void merge(vector<int> arr, int start, int end, vector<int> result) 
{int end1 = (start + end) / 2;int start2 = end1 + 1;// 用来遍历数组的指针int index1 = start;int index2 = start2;while (index1 <= end1 && index2 <= end) {if (arr[index1] <= arr[index2]) {result[index1 + index2 - start2] = arr[index1++];}else {result[index1 + index2 - start2] = arr[index2++];}}// 将剩余数字补到结果数组之后while (index1 <= end1) {result[index1 + index2 - start2] = arr[index1++];}while (index2 <= end) {result[index1 + index2 - start2] = arr[index2++];}// 将 result 操作区间的数字拷贝到 arr 数组中，以便下次比较while (start <= end) {arr[start] = result[start++];}
}void mergeSort(vector<int> arr) 
{if (arr.size() == 0) return;vector<int> result;mergeSort(arr, 0, arr.size() - 1, result);
}// 对 arr 的 [start, end] 区间归并排序
void mergeSort(vector<int> arr, int start, int end, vector<int> result)
{// 只剩下一个数字，停止拆分if (start == end) return;int middle = (start + end) / 2;// 拆分左边区域，并将归并排序的结果保存到 result 的 [start, middle] 区间mergeSort(arr, start, middle, result);// 拆分右边区域，并将归并排序的结果保存到 result 的 [middle + 1, end] 区间mergeSort(arr, middle + 1, end, result);// 合并左右区域到 result 的 [start, end] 区间merge(arr, start, end, result);
}

原地归并排序

实现一

// 将 arr 的 [start, middle] 和 [middle + 1, end] 区间合并
void merge(vector<int> arr, int start, int end) 
{int end1 = (start + end) / 2;int start2 = end1 + 1;// 用来遍历数组的指针int index1 = start;int index2 = start2;while (index1 <= end1 && index2 <= end) {if (arr[index1] <= arr[index2]) {index1++;}else {// 右边区域的这个数字比左边区域的数字小，于是它站了起来int value = arr[index2];int index = index2;// 前面的数字不断地后移while (index > index1) {arr[index] = arr[index - 1];index--;}// 这个数字坐到 index1 所在的位置上arr[index] = value;// 更新所有下标，使其前进一格index1++;index2++;end1++;}}
}// 对 arr 的 [start, end] 区间归并排序
void mergeSort(vector<int> arr, int start, int end)
{// 只剩下一个数字，停止拆分if (start == end) return;int middle = (start + end) / 2;// 拆分左边区域mergeSort(arr, start, middle);// 拆分右边区域mergeSort(arr, middle + 1, end);// 合并左右区域merge(arr, start, end);
}void mergeSort(vector<int> arr)
{if (arr.size() == 0) return;mergeSort(arr, 0, arr.size() - 1);
}

实现二

void exchange(vector<int> arr, int i, int j)
{int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}// 将 arr 的 [start, middle] 和 [middle + 1, end] 区间合并
void merge(vector<int> arr, int start, int end)
{int end1 = (start + end) / 2;int start2 = end1 + 1;// 用来遍历数组的指针int index1 = start;while (index1 <= end1 && start2 <= end) {if (arr[index1] > arr[start2]) {// 将 index1 和 start2 下标的数字交换exchange(arr, index1, start2);if (start2 != end) {// 调整交换到 start2 上的这个数字的位置，使右边区域继续保持有序int value = arr[start2];int index = start2;// 右边区域比 arr[start2] 小的数字不断前移while (index < end && arr[index + 1] < value) {arr[index] = arr[index + 1];index++;}// 交换到右边区域的这个数字找到了自己合适的位置，坐下arr[index] = value;}}index1++;}
}// 对 arr 的 [start, end] 区间归并排序
void mergeSort(vector<int> arr, int start, int end)
{// 只剩下一个数字，停止拆分if (start == end) return;int middle = (start + end) / 2;// 拆分左边区域mergeSort(arr, start, middle);// 拆分右边区域mergeSort(arr, middle + 1, end);// 合并左右区域merge(arr, start, end);
}void mergeSort(vector<int> arr) {if (arr.size() == 0) return;mergeSort(arr, 0, arr.size() - 1);
}