阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
说明：采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。
下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下：arr：待排序数组p，q，r：一个子数组的位置为从p到q，另一个子数组的位置为从q+1到rbegin，end：待排序数组的起止位置left，right：临时存放待合并的两个子数组n1，n2：两个子数组的长度i，j，k：循环变量mid：临时变量
问题1：根据以上说明和C代码，填充C代码中的空（1）～（4）。
问题2：根据题干说明和以上C代码，算法采用了（5）算法设计策略。分析时间复杂度时，列出其递归式为（6），解得渐进时间复杂度为（7）（用O符号表示）。空间复杂度为（8）（用O符号表示）。
问题3：两个长度分别为n1和n2的已排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为（9）。
参考答案：
问题1（1）k<=r或k<r+1（2）arr［k］=right［j］（3）begin<end（4）mergeSort（arr，mid+1，enD.
问题2（5）分治（6）T（n）=2T（n/2）+n或T（n）=2T（n／2）+f（n）（f（n）为线性函数）（7）O（nlgn）（8）O（n）
问题3（9）n1+n2
解析：
本题考查算法设计、分析和C程序实现的知识，属于传统题目，考查点也与往年类似。归并排序是一种经典的排序算法，基本思想：把n个元素构成的数组分成两个n/2个元素构成的子数组，再进一步划分，一直到每个子数组仅包含1个元素，此时再把两两有序的数组合并成更大的有序数组，一直到整个数组有序为止。
问题1：本问题考查算法的实现。C程序中有两个函数，merge函数将两个有序数组合并成一个更大的有序数组。归并过程是首先将两个有序的子数组的元素分别放到left和right数组中，然后依次比较这两个数组中的元素，从小到大把元素放到an数组的特定元素中。包含空格（1）的for循环中，给出了将left和right元素放入arr中，放入的位置是从p到r，因此，空格（1）填写k<=r。在比较left［i］和right［j］元素时，若left［i］>right［j］，则应该把right［j］的值放入arr［k］中，因此空格（2）填写arr［k］=right［j］。mergeSort函数进行数组的排序。若数组元素个数大于1，则继续划分，因此空格（3）填写begin
问题3：本问题考查对算法的进一步分析。元素之间的比较次数就是merge函数的最后一个for循环体执行的次数，由于k从p到r，故循环体执行次数为r-p+1次，即n1+n2次。
