// Remember to compile with -pthread #include #include #include #include using std::cout; using std::endl; using std::vector; using std::random_shuffle; using std::swap; using std::is_sorted; using namespace std::chrono; const int ARR_SIZE = 20000; void bubble_down(vector::iterator cur, const vector::iterator &lo) { while (cur > lo && *cur < *(cur - 1)) { swap(*cur, *(cur - 1)); cur--; } } void merge(const vector::iterator &lo, const vector::iterator &hi) { auto cur = (hi - lo) / 2 + lo; while (cur < hi) { bubble_down(cur, lo); cur++; } } void sort(const vector::iterator &lo, const vector::iterator &hi) { if (hi - lo <= 1) { return; } auto mid = (hi - lo) / 2 + lo; sort(lo, mid); sort(mid, hi); merge(lo, hi); } int main(int argc, char** argv) { vector vec(ARR_SIZE); int i = 0; for (int& n : vec) { n = i++; } cout << "Shuffling..." << endl; random_shuffle(vec.begin(), vec.end()); cout << (is_sorted(vec.begin(), vec.end()) ? "" : "not ") << "sorted " << endl; cout << "Sorting..." << endl; steady_clock::time_point start = steady_clock::now(); sort(vec.begin(), vec.end()); steady_clock::time_point end = steady_clock::now(); cout << (is_sorted(vec.begin(), vec.end()) ? "" : "not ") << "sorted " << endl; duration span = duration_cast>(end - start); cout << "Took: " << span.count() << " seconds" << endl; return 0; }