二、阅读程序（程序输入不超过数组或字符串定义的范围；除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

程序（2）

#include <iostream>
using namespace std;

int a[100005], b[100005], n, m;

void very_quick_sort(int l, int r, int p, int q) {
    if (l >= r || p > q) { // ①
        return;
    }
    int mid = (l + r) / 2;
    int p0 = p - 1;
    int q0 = q + 1;
    for (int i = p; i <= q; i++) {
        if (a[i] > mid) b[++p0] = a[i];
        else            b[--q0] = a[i];
    }
    for (int i = p; i <= q; i++)
        a[i] = b[i];
    very_quick_sort(mid + 1, r, p, p0);
    very_quick_sort(l, mid, q0, q);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    very_quick_sort(1, m, 1, n);
    // ②
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

保证输入的 $n$ 不超过 $10^5$，$m$ 不超过 $10^9$，且 $1 \le a_1,a_2,\ldots,a_n \le m$。

1. 不认为 $n,m$ 同阶，即可能出现 $n$ 远大于 $m$ 或者 $m$ 远大于 $n$ 的情况。则该程序的最坏时间复杂度为（ ）。

{{ select(1) }}

• $\Theta(n^2+m^2)$
• $\Theta(m\log m)$
• $\Theta(m\log n)$
• $\Theta(n\log m)$