写了一个先分成 $\sqrt n$ 块，然后对这 $\sqrt n$ 块用快速排序进行块内排序，然后归并排序合并这 $\sqrt n$ 块。可以通过排序模板。感觉平均时间复杂度是 $O(n \log\sqrt n$ $)$ 的，但是不太清楚，能帮忙算一下时间复杂度吗？

#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
ll blocks, n, a[1000005], le[1000005], re[1000005], b[1000005], cnt;
void merge(ll sl, ll sr, ll el, ll er){
    ll tot = le[sl] - 1;
    ll i = le[sl], j = le[el];
    while (i <= re[sr] && j <= re[er]){
        if (a[i] < a[j]){
            b[++tot] = a[i];
            i++;
        }else{
            b[++tot] = a[j];
            j++;
        }
    }
    while (i <= re[sr]){
        b[++tot] = a[i];
        i++;
    }
    while (j <= re[er]){
        b[++tot] = a[j];
        j++;
    }
    for (ll s = le[sl]; s <= re[er]; s++){
        a[s] = b[s];
    }
    return ;
}
void merge_sort(ll l, ll r){
    if (l < r){
        ll mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        merge(l, mid, mid + 1, r);
    }
    return ;
}
ll rnd(ll l, ll r){
    return rand() % (r - l + 1) + l;
}
void quick_sort(ll l, ll r){
    ll mid = a[rnd(l, r)], i = l, j = r;
    while (i <= j){
        while (a[i] < mid){
            i++;
        }
        while (a[j] > mid){
            j--;
        }
        if (i <= j){
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    if (i < r){
        quick_sort(i, r);
    }
    if (j > l){
        quick_sort(l, j);
    }
    return ;
}
int main(){
    srand(time(0));
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    blocks = sqrt(n);
    ll l = 1, r = blocks;
    cnt = n / blocks;
    for (ll i = 1; i <= n / blocks; i++){
        le[i] = l;
        re[i] = r;
        quick_sort(l, r);
        l += blocks;
        r += blocks;
    }
    if (l <= n){
        quick_sort(l, n);
        le[++cnt] = l;
        re[cnt] = n;
    }
    merge_sort(1, cnt);
    for (ll i = 1; i <= n; i++){
        printf("%lld ", a[i]);
    }
    return 0;
}