Merge sort bench

merge_bench.cpp

#include<bits/stdc++.h>

void merge(std::vector<int> &a, int l, int mid, int r) {
    int p1 = l;
    int p2 = mid + 1;

    std::vector<int> ret(r - l + 1);

    int i = 0;
    while (p1 <= mid && p2 <= r) ret[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];

    for (; p1 <= mid; p1++) ret[i++] = a[p1];
    for (; p2 <= r; p2++) ret[i++] = a[p2];

    std::copy(ret.begin(), ret.end(), a.begin() + l);
}

// L and r are inclusive
void merge_sort(std::vector<int> &a, int l, int r) {
    if (l < r) {
        int q = (l + r) / 2;
        merge_sort(a, l, q);
        merge_sort(a, q + 1, r);
        merge(a, l, q, r);
    }
}

int main() {
    std::vector<int> sizes {10, 100, 1000, 10000, 50000, 100000, 500000, 1000000, 5000000};
    std::cout << "input,time\n";
    for (int i : sizes) {
        std::vector<int> f(i );
        std::generate(f.begin(), f.end(), [](){ return std::rand() % 10000; });
        auto n1 = std::clock();
        merge_sort(f, 0, f.size() - 1);
        std::cout << i << ',' << (1000000 * (double)(std::clock() - n1) / CLOCKS_PER_SEC) << "\n";
    }
}