wfxr
10/26/2016 - 1:30 PM

## 归并排序的非递归实现，远快于标准库stable_sort

``````#include <numeric>
#include <chrono>
#include <vector>
#include <random>
#include <iostream>
#include <algorithm>

using namespace std;

using Iter = int*;
void merge(Iter l, Iter m, Iter u, Iter aux) {
auto p1 = l, p2 = m;
while (p1 != m && p2 != u)
*aux++ = *p2 < *p1 ? *p2++ : *p1++;
while (p1 != m) *aux++ = *p1++;
while (p2 != u) *aux++ = *p2++;
while (u > l) *--u = *--aux;
}

void merge_sort(vector<int> &a) {
auto aux = a;
const auto beg = a.data(), end = beg + a.size();
for (auto k = 1u; k < a.size(); k <<= 1)
for (auto u = beg; u != end;) {
auto m = u + k;
if (m >= end) break;
u = min(m + k, end);
merge(m - k, m, u, aux.data());
}
}
int main() {
vector<int> a(1'000'000);
//vector<int> a(000'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;
}``````