#include <vector>
#include <chrono>
#include <random>
#include <cstdlib>
#include <iostream>
#include <algorithm>
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main() {
std::vector<int> values;
values.reserve(100000);
std::random_device rd;
std::uniform_int_distribution<int> dist;
std::mt19937 eng(rd());
for(std::size_t i=0; i!=100000; ++i) {
values.push_back(dist(eng));
}
std::vector<int> values2(values);
{
auto n=std::chrono::high_resolution_clock::now();
std::qsort (values.data(), values.size(), sizeof(int), compare);
auto t=std::chrono::high_resolution_clock::now() - n;
std::cout << t.count() << std::endl;
}
{
auto n=std::chrono::high_resolution_clock::now();
std::sort(values2.begin(), values2.end());
auto t=std::chrono::high_resolution_clock::now() - n;
std::cout << t.count() << std::endl;
}
}
ICAgICNpbmNsdWRlIDx2ZWN0b3I+CiAgICAjaW5jbHVkZSA8Y2hyb25vPgogICAgI2luY2x1ZGUgPHJhbmRvbT4KICAgICNpbmNsdWRlIDxjc3RkbGliPgogICAgI2luY2x1ZGUgPGlvc3RyZWFtPgogICAgI2luY2x1ZGUgPGFsZ29yaXRobT4KICAgIAogICAgaW50IGNvbXBhcmUgKGNvbnN0IHZvaWQgKiBhLCBjb25zdCB2b2lkICogYikKICAgIHsKICAgICAgICByZXR1cm4gKCAqKGludCopYSAtICooaW50KiliICk7CiAgICB9IAogICAgCiAgICAKICAgIGludCBtYWluKCkgewogICAgICAgIHN0ZDo6dmVjdG9yPGludD4gdmFsdWVzOwogICAgICAgIHZhbHVlcy5yZXNlcnZlKDEwMDAwMCk7CiAgICAgICAgc3RkOjpyYW5kb21fZGV2aWNlIHJkOwogICAgICAgIHN0ZDo6dW5pZm9ybV9pbnRfZGlzdHJpYnV0aW9uPGludD4gZGlzdDsKICAgICAgICBzdGQ6Om10MTk5MzcgZW5nKHJkKCkpOwogICAgICAgIGZvcihzdGQ6OnNpemVfdCBpPTA7IGkhPTEwMDAwMDsgKytpKSB7CiAgICAgICAgICAgICAgICB2YWx1ZXMucHVzaF9iYWNrKGRpc3QoZW5nKSk7CiAgICAgICAgfQogICAgICAgIHN0ZDo6dmVjdG9yPGludD4gdmFsdWVzMih2YWx1ZXMpOwogICAgCiAgICAgICAgewogICAgICAgICAgICAgICAgYXV0byBuPXN0ZDo6Y2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpOwogICAgICAgICAgICAgICAgICAgICAgICBzdGQ6OnFzb3J0ICh2YWx1ZXMuZGF0YSgpLCB2YWx1ZXMuc2l6ZSgpLCBzaXplb2YoaW50KSwgY29tcGFyZSk7CiAgICAgICAgICAgICAgICBhdXRvIHQ9c3RkOjpjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCkgLSBuOwogICAgICAgICAgICAgICAgc3RkOjpjb3V0IDw8IHQuY291bnQoKSA8PCBzdGQ6OmVuZGw7CiAgICAgICAgfQogICAgICAgIHsKICAgICAgICAgICAgICAgIGF1dG8gbj1zdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsKICAgIAogICAgICAgICAgICAgICAgICAgICAgICBzdGQ6OnNvcnQodmFsdWVzMi5iZWdpbigpLCB2YWx1ZXMyLmVuZCgpKTsKICAgIAogICAgICAgICAgICAgICAgYXV0byB0PXN0ZDo6Y2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpIC0gbjsKICAgICAgICAgICAgICAgIHN0ZDo6Y291dCA8PCB0LmNvdW50KCkgPDwgc3RkOjplbmRsOwogICAgICAgIH0KICAgIAogICAgfQ==