归并排序的非递归实现,慢于标准库
#include <numeric>
#include <chrono>
#include <vector>
#include <random>
#include <iostream>
#include <algorithm>
using namespace std;
void merge(vector<int> &a, size_t l, size_t m, size_t u, vector<int> &aux) {
auto p1 = l, p2 = m, pos = l;
while (p1 != m && p2 != u)
aux[pos++] = a[p2] < a[p1] ? a[p2++] : a[p1++];
while (p1 != m) aux[pos++] = a[p1++];
while (p2 != u) aux[pos++] = a[p2++];
for (auto i = l; i < u; ++i) a[i] = aux[i];
}
void merge_sort(vector<int> &a) {
auto n = a.size();
auto aux = a;
for (auto k = 1u; k < n; k <<= 1)
for (auto u = 0u; u <= n;) {
auto m = u + k;
if (m >= n) break;
u = min(m + k, n);
merge(a, m - k, m, u, aux);
}
}
int main() {
vector<int> a(100'000);
iota(a.begin(), a.end(), 0);
random_device rd;
mt19937 gen(rd());
shuffle(a.begin(), a.end(), gen);
auto t1 = chrono::system_clock::now();
merge_sort(a);
//stable_sort(a.begin(), a.end());
auto t2 = chrono::system_clock::now();
cout << (is_sorted(a.begin(), a.end()) ? "" : "Not ") << "Sorted" << endl;
cout << "Time used: " << chrono::duration<double>(t2 - t1).count() << "s" << endl;
return 0;
}