非递归代码：

/***************************************************************** @description: merge sort* @author: kashine* @version: 1.0* @mail: likaiqinchina@gmail.com* @date: 2022/12/29
****************************************************************/
#include 
#include using namespace std;void merge(vector& array, int start, int mid, int end)
{// [start, mid]左侧有序, [mid + 1, end]右侧有序int n1 = mid - start + 1;// 左侧有序int n2 = end - mid;// 右侧有序// 将左右侧有序部分分别存储到temp1，temp2中vector temp1, temp2;int i = 0, j = 0;while(i < n1)temp1.emplace_back(array[start + i++]);while(j < n2)temp2.emplace_back(array[mid + 1 + j++]);// 将temp1，temp2按顺序归并到array中i = 0; j = 0;int k = start;// 注意：k不能等于0！！！while(i < n1 && j < n2){if(temp1[i] < temp2[j]){array[k++] = temp1[i++];}else{array[k++] = temp2[j++];}}// 将剩余元素拷贝到array中while(i < n1)array[k++] = temp1[i++];while(j < n2)array[k++] = temp2[j++];}void mergeSort(vector& arr) {int n = arr.size();for (int curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size) {for (int left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {int mid = left_start + curr_size - 1;int right_end = std::min(left_start + 2 * curr_size - 1, n - 1);merge(arr, left_start, mid, right_end);}}
}int main() {vector arr = {38, 27, 43, 3, 9, 82, 10};mergeSort(arr);for (int i = 0; i < arr.size(); i++)std::cout << arr[i] << " ";std::cout << std::endl;return 0;
}

🥝 算法复杂度：

合并复杂度O(n)，分治复杂度：T(n) = 2T(n/2) + O(n)，类似于快速排序每一次取到的元素都刚好平分整个数组的情况。详细推导见：快速排序时间复杂度分析 - 知乎排序算法之 快速排序 及其时间复杂度和空间复杂度

最好时间复杂度：O(nlog2n)

最坏时间复杂度：O(nlog2n)

空间复杂度：O(n)

因为不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )。

详见排序算法之 归并排序 及其时间复杂度和空间复杂度

🥝 改进方案：

归并排序的时间复杂度为O(nlgn)，一般来讲，基于从单个记录开始两两归并的排序并不是特别提倡，一 种比较常用的改进就是结合插入排序，即先利用插入排序获得较长的有序子序列，然后再两两归并（改进后的归并仍是稳定的，因为插入排序是稳定的）。