在对长度为n(n≥1) 的数组进行归并排序的过程中,mergeArray 函数(合并两个有序子数组的操作)被调用的次数是
MAXN = 100005
a = [0] * MAXN
tempArr = [0] * MAXN
def mergeArray(left, mid, right):
i = left
j = mid + 1
k = left
while i <= mid and j <= right:
if a[i] <= a[j]:
tempArr[k] = a[i]
i += 1
else:
tempArr[k] = a[j]
j += 1
k += 1
while i <= mid:
tempArr[k] = a[i]
i += 1
k += 1
while j <= right:
tempArr[k] = a[j]
j += 1
k += 1
for p in range(left, right + 1):
a[p] = tempArr[p]
def mergeSort(left, right):
if left >= right:
return
mid = left + (right - left) // 2
mergeSort(left, mid)
mergeSort(mid + 1, right)
mergeArray(left, mid, right)
n-1
long n
n long n
2n