#include <stdio.h>
#include <stdint.h>
#include <atomic>
#include <thread>
#include <vector>
#include <mutex>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <future>

using namespace std;

void merge(int* begin1, int* end1, int* begin2, int* end2, int* merged)
{
    int* curr1 = begin1;
    int* curr2 = begin2;
    while(curr1<end1 || curr2<end2) {
        if(curr2>=end2 || (curr1<end1 && *curr1<*curr2)) {
            *merged = *curr1;
            ++curr1;
        } else {
            *merged = *curr2;
            ++curr2;
        }
        ++merged;
    }
}

void mergeSortRec(size_t n, int* in, int* buf, bool putResultInInput, size_t nrThreads)
{
    if(n <= 1) {
        if(!putResultInInput & n == 1) {
            *buf = *in;
        }
        return;
    }
    size_t k = n/2;
    if(nrThreads >= 2) {
        size_t th = nrThreads/2;
        future<void> ff = async(launch::async, [k,in,buf,putResultInInput,th]()->void{mergeSortRec(k, in, buf, !putResultInInput, th);});
        mergeSortRec(n-k, in+k, buf+k, !putResultInInput, 1);
        ff.wait();
    } else {
        mergeSortRec(k, in, buf, !putResultInInput, 1);
        mergeSortRec(n-k, in+k, buf+k, !putResultInInput, 1);
    }
    if(putResultInInput) {
        merge(buf, buf+k, buf+k, buf+n, in);
    } else {
        merge(in, in+k, in+k, in+n, buf);
    }
}

void mergeSort(int* v, size_t n, size_t nrThreads)
{
    unique_ptr<int[]> buf { new int[n] };
    mergeSortRec(n, v, buf.get(), true, nrThreads);
}

void generate(int* v, size_t n, size_t nrThreads)
{
    vector<future<void>> futures;
    futures.reserve(nrThreads);
    size_t start = 0;
    for(size_t th=0 ; th<nrThreads ; ++th) {
        size_t sz = (n-start)/(nrThreads-th);
        futures.push_back(async([v,start,sz]()->void {
            for(size_t i=0 ; i<sz ; ++i) {
                //v[start+i]=rand();
                v[start+i]=(i*101) % 123456;
            }
        }));
        start += sz;
    }
    for(future<void>& f : futures) {
        f.wait();
    }
}

bool isSorted(int const* const& v, size_t n)
{
    for(size_t i=1 ; i<n ; ++i) {
        if(v[i-1]>v[i]) return false;
    }
    return true;
}

int main(int argc, char** argv)
{
    size_t n = 0;
    size_t nrThreads = 0;
    if(argc != 3 || 1!=sscanf(argv[1], "%u", &n) || 1!=sscanf(argv[2], "%u", &nrThreads)){
        fprintf(stderr, "usage: mergesort <n> <nrThreads>\n");
        return 1;
    }
    unique_ptr<int[]> v{new int[n]};
    generate(v.get(), n, nrThreads);
    fprintf(stderr, "generated\n");
    chrono::high_resolution_clock::time_point const beginTime = chrono::high_resolution_clock::now();
    
    mergeSort(v.get(), n, nrThreads);
    
    chrono::high_resolution_clock::time_point const endTime = chrono::high_resolution_clock::now();

    cout << (isSorted(v.get(), n) ? "ok" : "WRONG") << "; time="<<  (chrono::duration_cast<chrono::milliseconds>(endTime-beginTime)).count() <<"ms\n";
}