#include<bits/stdc++.h>
using namespace std;
void Mergearray(int a[],int first,int mid,int last,int temp[]) //将两个有序数组合并排序
{
int i=first,j=mid+1;
int m=mid,n=last;
int k=0;
while(i<=m&&j<=n)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=m)
temp[k++]=a[i++];
while(j<=n)
temp[k++]=a[j++];
for(i=0;i<k;i++)
a[first+i]=temp[i];
}
void Mergesort(int a[],int first,int last,int temp[]) //将两个任意数组合并排序
{
if(first<last)
{
int mid=(first+last)/2;
Mergesort(a,first,mid,temp); //左边有序
Mergesort(a,mid+1,last,temp); //右边有序
Mergearray(a,first,mid,last,temp); //再将两个有序数组合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n]; //分配一个有n个int型元素的数组所占空间，并将该数组的第一个元素的地址赋给int *型指针p。
if (p == NULL)
return false;
Mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
int main()
{
int a[1000];
int n;
printf("请输入数的个数：\n");
scanf("%d",&n);
printf("请输入要排序的数列：\n");
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
MergeSort(a,n);
printf("排序结果为：");
for(int i=0;i<n;i++)
printf(" %d ",a[i]);
}
