阅读下列说明和C代码，回答下列问题。[说明]???采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排序的子数组得到排序结果。???下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下：???arr:待排序数组???P,q,r:一个子数组的位置从P到q，另一个子数组的位置从q+1到r???begin,end:待排序数组的起止位量???left,right:临时存放待合并的两个子数组???n1,n2:两个子数组的长度???i,j,k:循环变量???mid:临耐变量???[C代码]???#inciude＜stdio,h＞???#include＜stdlib,h＞???DefineMAX65536???voidmerge(intarr[],intp,intq,intr){???int*left,*right;???intn1,n2,I,j,k;???n1=q-p+1;???n2=r-q;???If(left=(int*)malloc((n1+1)*sizeof(int)))=NULL){???Perror("mallocerror");???exit11???}???If((right=(int*)malloc((n2+1)*sizeof(int)))=NULL)???Perror("mallocerror");???exit11;???}???for(i=0;i＜n1;i++){???left[i]=arr[p+i];???}???left[i]=MAX;???for(i=0;i＜n2;i++){???right[i]=arr[q+i+1]???}???right[i]=MAX;???i=0;j=0;???For(k=p;______;k++){???If(left[i]＞right[j]{???______???j++;???}else{???arr[k1]=left[i];???i++;???}???}???}???VoidmergeSort(intarr[],intbegin,intend){???intmid;???if(______){???mid=(begin+end)/2;???mergeSort(arr,begin,mid);???______;???Merge(arr,begin,mid,end);???}???}
11、k＜=r arr[k]=right[j] begin＜end mergeSort(arr,mid+1,end)[解析] 首先，函数void merge(int arr[],int P,int q,int r)的意思是：对子数组arr[P…q]和子数组arr[q+L..r]进行合并。因此第一空为k＜=q；由于是采用归并排序对n个元素进行递增排序，所以第二空是将left[i]和right[j]的小者存放到arr[k]中去，即arr[k]=right[j]：当数组长度为1时，停止递归，因为此时该数组有序，则第三空为begin＜end，即数组至少有两个元素才进行递归。合并了begin到mid之间的元素，继续合并mid+1到end之间的元素，则第四空为mergeSort(arr,mid+1,end)。12、分治 T(n)=2T(n/2)+O(n) O(nlogn) O(n)[解析] 归并算法实际上就是将数组一直往下分割，直到分割到由一个元素组成的n个子数组，再往上两两归并。 将数组进行分割需要logN步，因为每次都是讲数组分割成两半(2x=N，x=logN)。 合并N个元素，需要进行N步，也就是O(N)，则总的时间复杂度为O(NlogN)。 合并过程中，使用了”个中间变量存储，left=(int*)malloc((n1+1)*sizeof(int))。所以空间复杂度为O(n)。 推导递归式：假设n个元素进行归并排序需要T(n)，可以将其分割成两个分别有n/2个元素的数组分别进行归并，也就是2T(n/2)，在将这两个合并，需要O(n)的时间复杂度，则推导公式为T(n)=2T(n/2)+O(n)。13、n1+n2
