在对长度为 n 的数组进行归并排序的过程中, mergeArray 函数(合并两个有序子数组的操作) 被调用的次数是( )。

const int MAXN = 100005;
int a[MAXN];
int tempArr[MAXN];
void mergeArray(int left, int mid, int right) {
    int i = left; // 左半部分起点
    int j = mid + 1; // 右半部分起点
    int k = left; // 临时数组下标
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            tempArr[k++] = a[i++];
        } else {
            tempArr[k++] = a[j++];
        }
    }
    while (i <= mid) {
        tempArr[k++] = a[i++];
    }
    while (j <= right) {
        tempArr[k++] = a[j++];
    }
    for (int p = left; p <= right; p++) {
        a[p] = tempArr[p];
    }
}
void mergeSort(int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(left, mid);
    mergeSort(mid + 1, right);
    mergeArray(left, mid, right);
}

{{ select(1) }}

• $n - 1$
• $\log n$
• $n \log n$
• $2n$