单选题 适中
#20899

考虑以下C++代码实现的归并排序算法: void merge ( int arr [ ] , int left , int mid , int right )…

考虑以下C++代码实现的归并排序算法:

void merge(int arr[], int left, int mid, int right) {
	int n1 = mid - left + 1;
	int n2 = right - mid;
	
	int L[n1], R[n2];
	
	for (int i = 0; i < n1; i++)
		L[i] = arr[left + i];
	for (int j = 0; j < n2; j++)
		R[j] = arr[mid + 1 + j];
		
	int i = 0, j = 0, k = left;
	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}
	
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}
	
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

void merge_sort(int arr[], int left, int right) {
	if (left < right) {
		int mid = left + (right - left) / 2;
		
		merge_sort(arr, left, mid);
		merge_sort(arr, mid + 1, right);
		
		merge(arr, left, mid, right);
	}
}

对长度为 n 的数组 arr ,挑用函数 merge_sort(a, 0, n-1) ,在排序过程中 merge 函数的递归调用次数大约是( )。

未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析

merge_sort函数的作用是递归进行分治的过程,每次把序列分成两半,然后分别处理,merge函数的作用是把两个有序序列,通过双指针操作,合并为一个有序序列。merge函数的调用次数,先是两个数的合并,执行次数为n/2,然后是4个数合并,执行次数为n/4……大约为O(n)