归并排序的概要
1.核心思想
归并排序属于排序方式的一种，相比于冒泡排序其速度要快很多，稍次于快速排序。该方法的重要思想为分治法，首先将整个数据从中间一分为二，然后左右俩边再重复上述操作，直至分为每个子段只有一个数，这时候我们可以认为这个子段是有序的了，然后俩俩相比较合并达到排序效果，其排序类型为稳定排序。
2.代码
#include <stdio.h>
#include <stdlib.h>
void Merge(int Arr1[],int Arr2[], int start, int mid, int end)
//start是数组头元素,mid是中间值，因为要从中间一分为二，end就是结尾啦
{
int i = start, j=mid+1, k = start;
while(i!=mid+1 && j!=end+1)
{
if(Arr1[i] > Arr1[j])
Arr2[k++] = Arr1[j++];
else
Arr2[k++] = Arr1[i++];
}
//如果最后俩个数组合并后有一个没用完，那没用完的数一定有序，依次加在后面即可
while(i != mid+1)
Arr2[k++] =Arr1[i++];
while(j != end+1)
Arr2[k++] = Arr1[j++];
for(i=start; i<=end; i++)
Arr1[i] = Arr2[i];
}
void Sort(int Arr1[], int Arr2[], int start, int end)
{
int mid;
if(start!=end)
{
mid = start + (end-start) / 2;
Sort(Arr1, Arr2, start, mid);
Sort(Arr1,Arr2, mid+1,end);//递归，直至每个子段只有一个元素
Merge(Arr1, Arr2, start, mid, end);
}
}
int main()
{
int i,n;
while(~scanf("%d",&n))
{
while(n--)
{
int m;
scanf("%d",&m);
int a[100010]={0},b[100010]={0};
for(i=0;i<m;i++)
scanf("%d",&a[i]);
Sort(a, b, 0,m-1);
for(i=0;i<m;i++)
printf("%d ",a[i]);
printf("\n");
}
}
return 0;
}