参考答案:

【问题1】（8分）
（1）k<=r
（2）arr[k]=right[j]
（3）begin<end
（4）mergeSort(arr,mid+1,end)

【问题2】（5分）
（5）分治
（6）T(n)=2T(n/2)+n
（7）O(nlgn)
（8）O(n)

【问题3】（2分）
（9）n1+n2

详细解析:

根据题目中的参数说明，void  merge(int arr[],int p,int q,int r)是将数组arr[p...q]和数组arr[q+1...r]进行合并成一个排序的数组，因此合并之后数组的长度为r-q+1>0，k=q，也就是k<=r或k<r+1；数组arr存入子数组arr[p...q]、arr[q+1...r]当前进行比较的最小值，因此当left[i]> right[j]时，数组arr中存入right[i]，即arr[k]=right[j]；
void mergeSort(int arr[],int begin,int end)是指将数组arr递归进行划分，直到分成多个由一个元素组成的子数组时，停止划分，此时也就是begin==end，因此（3）处为begin<end，也就是只要begin!=end则继续划分。划分的时候每次分成两半，两半再分别递归，因此mergeSort(arr,begin,mid);mergeSort(arr,mid+1,end);
很明显归并排序使用的分治算法，每次将数组分割成两个小的子数组。
假设对n个元素的数组进行归并排序时间复杂度为T(n)，则分成两个小的子数组后分别进行排序所需的时间为T(n/2)，两个子数组则时间复杂度为2T(n/2)，再加上归并的时间n，即可得出答案归并排序的时间复杂度为O(nlgn)，因为在归并过程中，需要借助left和right两个数组辅助，因此空间复杂度为O(n)。