https://www.luogu.com.cn/article/k8nh9vo0

看了漫士的这期视频，我忽然发现，std::sort 竟是 $\Theta(N \log N)$ 的，便马上做了个实验，Amazing啊，竟然有点符合本福特定律，以下是实验数据：

Avg_N = 5.06609e+06, Avg_time = 0.230004 s
P[1] = 0.229492
P[2] = 0.246826
P[3] = 0.234131
P[4] = 0.168091
P[5] = 0.0266113
P[6] = 0.0234375
P[7] = 0.0255127
P[8] = 0.0220947
P[9] = 0.0238037

也有可能是随机的数据有问题？希望知道的给一个答复。

代码（g++-14 main.cpp -o main -O2 -march=native）：https://www.luogu.com.cn/paste/bilcktnw

main.cpp

#include <algorithm>
#include <ctime>
#include <iostream>
#include <numeric>
#include <random>

constexpr unsigned Tests = 8192;

clock_t run(unsigned n, unsigned* arr) {
    auto start = clock();
    std::sort(arr, arr + n);
    return clock() - start;
}

int main() {
    using namespace std;
    unsigned long cnt[10]{};
    double nsum = 0, tsum = 0;
    default_random_engine rnd(time(nullptr));
    uniform_int_distribution ndis(10000, 9999999);
    for (int i = 0; i < Tests; i++)
    {
        int n = ndis(rnd);
        nsum += n;
        cout << "Running Test " << i << ", N = " << n << "\n";
        auto arr = new unsigned[n];
        for (int j = 0; j < n; j++)
            arr[j] = rnd();
        auto res = run(n, arr);
        tsum += static_cast<double>(res) / CLOCKS_PER_SEC;
        while (res > 9)
            res /= 10;
        ++cnt[res];
        delete[] arr;
    }
    unsigned long tot = accumulate(cnt + 1, cnt + 10, 0ul);
    cout << "Avg_N = " << nsum / Tests << ", Avg_time = " << tsum / Tests << " s\n";
    for (int i = 1; i < 10; i++)
        cout << "P[" << i << "] = "
                << static_cast<double>(cnt[i]) / tot << endl;
    return 0;
}