//
//  main.cpp
//  AK
//
//  Created by Irina Scherbitskaya on 11/16/18.
//  Copyright © 2018 Irina Scherbitskaya. All rights reserved.
//

#include <iostream>


int* merge(int* arr1, int* arr2, int n1, int n2){
    int* ans =  new int[n1+n2];
    int cur1 = 0, cur2 = 0;
    for(int i = 0; i < n1+n2; i++)
        if (arr1[cur1] < arr2[cur2]){
            ans[i] = arr1[cur1];
            cur1++;
        }
        else {
            ans[i] = arr2[cur2];
            cur2++;
        }
    return ans;
}

int main(int argc, const char * argv[]) {
    int* array;
    int size;
    int rank = MPI::COMM_WORLD.Get_rank();
    int nthreat;
    int* current;
    int root = 0;
    int n1_size, n2_size;
    int* arr1, arr2;
    if (size % nthreat == 0)
        n1_size = n2_size = size/nthreat;
    else {
        n1_size = size/nthreat + 1;
        n2_size = (size/nthreat + 1)*nthreat - size;
    }

    MPI::COMM_WORLD.Scatter(&values, n1_size, MPI::INT, &current, n1_size, MPI::INT, root);
    std::sort(current, current + n1_size);
    for (int i = 2; i < size; i*=2){
        if (rank % i == 0 && rank != nthreat - 1){
            int n2 = n1_size;
            MPI::COMM_WORLD.Recv(&arr1, n1_size, MPI::INT, rank, tag);
            if (rank + i/2 == nthreat - 1)
                n2 = n2_size;
            MPI::COMM_WORLD.Recv(&arr2, n2, MPI::INT, rank + i/2, tag);
            int* current merge(arr1, arr2, n1_size, n2)
            MPI::COMM_WORLD.Send(&current, n1_size+n2, MPI::INT, rank, tag);
        }
        MPI::COMM_WORLD.Barrier();
    }
    return 0;
}