/*
归并排序
思想：
1.分而治之，将一个无序的数列一直一分为二，直到分到序列中只有一个数的时候，这个序列肯定是有序的，因为只有一个数，然后将两个只含有一个数字的序列合并为含有两个数字的有序序列，这样一直进行下去，最后就变成了一个大的有序数列
2.递归的结束条件是分到最小的序列只有一个数字的时候
时间复杂度分析：
最坏情况：T(n)=O(n*lg n)
平均情况：T(n)=O(n*lg n)
稳定性：稳定（两个数相等的情况，不用移动位置
辅助空间：O(n)
特点总结：
高效
耗内存（需要一个同目标数组SR相同大小的数组来运行算法）
*/
#include<stdio.h>
#define max 1024
int SR[max],TR[max];
int merge(int SR[],int TR[],int s,int m,int t)//SR代表两个有序序列构成的序列，s表示起始位置，m表示两个序列的分解位置，但是SR[m]仍是属于前面一个序列，t表示结束位置
{//TR是一个空数组，用来存放排序好之后的数字
int i=s,j=m+1,k=s;
while(i<=m&&j<=t)
{
if(SR[i]<SR[j])
{
TR[k++]=SR[i++];
}else
{
TR[k++]=SR[j++];
}
}
while(i<=m)//当前面一个序列有剩余的时候，直接把剩余数字放在TR的后面
{
TR[k++]=SR[i++];
}
while(j<=t)//当后面一个序列有剩余的时候，直接把剩余数字放在TR的后面
{
TR[k++]=SR[j++];
}
return 0;
}//该函数要求SR是由两个有序序列构成
void copy(int SR[],int TR[],int s,int t)//把TR赋给SR
{
int i;
for(i=s;i<=t;i++)
{
SR[i]=TR[i];
}
}
int mergesort(int SR[],int s,int t)
{
if(s<t)//表示从s到t有多个数字
{
int m=(s+t)/2;//将序列一分为二
mergesort(SR,s,m);//前一半序列继续进行归并排序
mergesort(SR,m+1,t);//后一半序列同时进行归并排序，
//以上递归调用的结束条件是s!<t,也就是进行分到只有一个数字进行归并排序的时候，一个序列只有一个数字，那么这个序列肯定是有序的
//以上都是属于“分”的阶段，目的是获得两个有序的数列
merge(SR,TR,s,m,t);//对这两个有序的数列，进行排序，变成一个同样大小但是有序的数列
copy(SR,TR,s,t);//将在TR中排序好的数列给SR，方便SR递归调用归并排序，因为每次两个归并排序的结果都是保存在TR中的，现在要进行下一步就必须在TR数列的基础上面=进行，所以我们把TR给SR
}else//表示从s到t只有一个数字（s==t），或者没有数字（s>t）
{
;//空，也可省略，加一个else只是为了更好的理解程序
}
return 0;
}
int main()
{
int n;
printf("请输入排序数字的个数:
");
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
{
scanf("%d",&SR[i]);
}
mergesort(SR,0,n-1);//升序排列
for(i=0;i<n;i++)
{
printf("%d ",SR[i]);
}
printf("
");
return 0;
}