空间复杂度原因是因为需要额外数组空间来进行排序

时间复杂度 T(n)=2T(n/2)+O(n),a=2,b=2,c=1根据master公式可知时间复杂度O(nlogN)

归并排序可以排序数据量很大的数组,举例说明,例如要排序有2^64个数字的数组,那么归并排序将会开辟64层系统栈,这并不会导致栈溢出.

include

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]

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

mergeSort(a,left,mid);

mergeSort(a,mid+1,right);

merge(a,left,mid,right);

}

}