两种排序的最坏比较次数

把五个元素的全部 120 种排列都跑一遍，插入排序和归并排序各自最坏比了多少次：

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> merge_go(const vector<int>& x, int& c) {
    if (x.size() <= 1) return x;
    size_t m = x.size() / 2;
    vector<int> L = merge_go(vector<int>(x.begin(), x.begin() + m), c);
    vector<int> R = merge_go(vector<int>(x.begin() + m, x.end()), c);
    vector<int> out;
    size_t i = 0, j = 0;
    while (i < L.size() && j < R.size()) {
        c++;
        if (L[i] <= R[j]) out.push_back(L[i++]);
        else out.push_back(R[j++]);
    }
    out.insert(out.end(), L.begin() + i, L.end());
    out.insert(out.end(), R.begin() + j, R.end());
    return out;
}

int merge_cmp(const vector<int>& a) {   // 归并排序，返回比较次数
    int c = 0;
    merge_go(a, c);
    return c;
}

int ins_cmp(vector<int> a) {            // 插入排序，返回比较次数
    int c = 0;
    for (size_t i = 1; i < a.size(); i++) {
        int x = a[i];
        int j = (int)i - 1;
        while (j >= 0) {
            c++;
            if (a[j] <= x) break;
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
    return c;
}

vector<vector<int>> all_perms() {
    vector<int> p = {0, 1, 2, 3, 4};
    vector<vector<int>> out;
    do { out.push_back(p); } while (next_permutation(p.begin(), p.end()));
    return out;
}

int main() {
    int wi = 0, wm = 0;
    for (const auto& p : all_perms()) {
        wi = max(wi, ins_cmp(p));
        wm = max(wm, merge_cmp(p));
    }
    cout << wi << "/" << wm << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）