空间复杂度原因是因为需要额外数组空间来进行排序
时间复杂度 T(n)=2T(n/2)+O(n),a=2,b=2,c=1根据master公式可知时间复杂度O(nlogN)
归并排序可以排序数据量很大的数组,举例说明,例如要排序有2^64个数字的数组,那么归并排序将会开辟64层系统栈,这并不会导致栈溢出.

include<stdio.h>

void merge(int a[],int left,int mid,int right){
int length=right-left+1;//5-0+1;因为有数组零下标的存在,所以要多加一
int temp[length]; //创建一个对应长度的数组
int i=left; //左指针
int j=mid+1; //右指针
int k=0; //记录temp数组的下标指针
//把较小的数移到新temp数组中
while(i<=mid&&j<=right){
if(a[i]<a[j]){
temp[k++]=a[i++];
}else{
temp[k++]=a[j++];
}
}
//把左边剩余的数移入数组
while(i<=mid){
temp[k++]=a[i++];
}
//把右边剩余的数移入数组
while(j<=right){
temp[k++]=a[j++];
}
for(int i=left;i<=right;i++){
a[i]=temp[i-left];//输入回原数组
}
}
void mergeSort(int a[],int left,int right){
int mid=(left+right)/2;
if(left<right){
mergeSort(a,left,mid);
mergeSort(a,mid+1,right);
merge(a,left,mid,right);
}
}