代码如下：
//算法思想：将两段有序的数据合并成一段有序的数据，直到所有数据有序
//或者将两段有序的数据归并为一段更有序的，也称2路归并
//时间复杂度：O(nlogn) 空间复杂度：O(n) 稳定性：稳定
#include<iostream>
#include<algorithm>
#include <stdio.h>
#include <cstdlib>
#include <cmath>
using namespace std;
void merge(int* nums, int low, int mid, int high)//合并函数
{
int* arr = new int[high - low + 1];//开辟一个新数组存放最终的结果
int i = low, j = mid + 1, k = 0;//k为开辟的新数组的下标
while (i <= mid && j <= high)
{
if (nums[i] <= nums[j])//按从小到大的顺序放到arr数组里
{
arr[k++] = nums[i++];
}
else
{
arr[k++] = nums[j++];
}
}
while (i <= mid)//j序列结束，将剩余的i序列补充在arr数组里
{
arr[k++] = nums[i++];
}
while (j <= high)
{
arr[k++] = nums[j++];//i序列结束，将剩余的j序列补充在arr数组里
}
k = 0;//从下标0开始传送
for (int i = low; i <= high; i++)//将arr数组里的值传送给数组nums
{
nums[i] = arr[k++];
}
delete[]arr;//辅助数组用完后，将其空间进行释放
}
void mergesort(int* nums, int low, int high)//归并排序
{
if (low < high)
{
int mid = (low + high) / 2;
mergesort(nums, low, mid);//对arr[low,mid]进行排序
mergesort(nums, mid + 1, high);//对arr[mid+1,high]进行排序
merge(nums, low, mid, high);//进行合并操作
}
}
int main()
{
int n, nums[200];
cout << "输入元素n的个数" << endl;
cin >> n;
cout << "依次输入数字" << endl;
for (int i = 0; i < n; i++)
{
cin >> nums[i];
}
mergesort(nums, 0, n - 1);
cout << "归并排序后的结果" << endl;
for (int i = 0; i < n; i++)
{
cout << nums[i] << " ";
}
cout << endl;
return 0;
}