使用benchmark比较插入排序与归并排序性能

#include <benchmark/benchmark.h>

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <random>
#include <string>
#include <vector>

using namespace std;

static const int _num = 3000;                // 待测试的数据量
static const int _range = 100000;            // 待测试的数据大小范围
static const int _iter = 100;                // 迭代运行次数

template <class T>
void insertion_sort(vector<T>& _array) {
    for (size_t j = 1; j < _array.size(); j++) {
        auto key = _array[j];
        size_t i = j - 1;
        while (i >= 0 && _array[i] > key) {
            _array[i + 1] = _array[i];
            i--;
        }
        _array[i + 1] = key;
    }
}

static void BM_demo_1(benchmark::State& state) {
    for (auto _ : state) {
        state.PauseTiming();
        vector<int> a;
        random_device rd;
        mt19937 gen(rd());
        uniform_int_distribution<int> dist(0, _range);
        for (int i = 0; i < _num; ++i) {
            a.push_back(dist(gen));
        }
        state.ResumeTiming();

        insertion_sort(a);
    }
}
BENCHMARK(BM_demo_1)->Iterations(_iter);

template <class T>
void merge(vector<T>& _array, size_t left, size_t right, size_t mid) {
    auto _larray = deque<T>(_array.begin() + left, _array.begin() + mid + 1);
    auto _rarray = deque<T>(_array.begin() + mid + 1, _array.begin() + right + 1);
    for (auto Iter = _array.begin() + left; Iter <= _array.begin() + right;
             Iter++) {
        if (_rarray.empty() == true) {
            *Iter = _larray.front();
            _larray.pop_front();
        } else if (_larray.empty() == true) {
            *Iter = _rarray.front();
            _rarray.pop_front();
        } else {
            if (_larray.front() > _rarray.front()) {
                *Iter = _larray.front();
                _larray.pop_front();
            } else {
                *Iter = _rarray.front();
                _rarray.pop_front();
            }
        }
    }
}

template <class T>
void merge_sort(vector<T>& _array, size_t left, size_t right) {
    if (left != right) {
        size_t mid = size_t((left + right) / 2);
        merge_sort(_array, left, mid);
        merge_sort(_array, mid + 1, right);
        merge(_array, left, right, mid);
        // inplace_merge(_array.begin() + left, _array.begin() + mid + 1,
        //                             _array.begin() + right + 1, greater<T>());
    }
}

static void BM_demo_2(benchmark::State& state) {
    for (auto _ : state) {
        state.PauseTiming();
        vector<int> a;
        random_device rd;
        mt19937 gen(rd());
        uniform_int_distribution<int> dist(0, _range);
        for (int i = 0; i < _num; ++i) {
            a.push_back(dist(gen));
        }
        state.ResumeTiming();

        merge_sort(a, 0, a.size() - 1);
    }
}
BENCHMARK(BM_demo_2)->Iterations(_iter);

BENCHMARK_MAIN();