#include <iostream>
#include <thread>

using namespace std;

struct argumento{
    int ini, fin, mid;
};
pthread_mutex_t mymutex = PTHREAD_MUTEX_INITIALIZER;

int A[101010];
void merge(int inicio, int meio, int fim){ //função merge normal
    int i=0, j=0, k=0;
    int temp[100000], p1, p2, tam;
    int fim1=0, fim2=0;
    tam = fim-inicio+1;
    p1 = inicio;
    p2=meio+1;
    for(i=0;i<tam;i++){
        if(!fim1 && !fim2){
            if(A[p1]<A[p2]){
                temp[i] = A[p1++];
            }
            else{
                temp[i] = A[p2++];
            }
            if(p1>meio){
                fim1 = 1;
            }
            if(p2>fim){
                fim2 = 1;
            }
        }
        else{
            if(!fim1){
                temp[i] = A[p1++];
            }
            else{
                temp[i] = A[p2++];
            }
        }
    }
    for(j=0,k=inicio;j<tam;j++,k++){
        A[k] = temp[j];
    }
}

void *merge_sort(void *argv){ //thread merge sort
    int inicio, meio, fim;
    argumento *argx = (argumento*)argv; //recebo o argumento e transfiro os valores
    inicio = argx->ini;
    fim = argx->fin;
    if(inicio<fim){
        meio = (inicio+fim)/2;
        pthread_t thread1, thread2;
        argumento *arg = new argumento; //declaro os argumentos das novas threads
        argumento *arg2 = new argumento;
        //merge_sort(inicio,meio);
        arg->ini = inicio; //escolho os argumentos das novas threads
        arg->fin = meio;
        arg2->ini = meio+1;
        arg2->fin = fim;
        pthread_create(&thread1, NULL, merge_sort, (void*)arg);

        //merge_sort(meio+1,fim);
        pthread_create(&thread2, NULL, merge_sort, (void*)arg2);

        pthread_join(thread1, NULL); //espero as threads
        pthread_join(thread2, NULL);

        //merge(inicio,meio,fim);
        merge(inicio, meio, fim);

    }
    pthread_exit(NULL);
}

int main() {
    cout << "Digite o tamanho do array: ";
    argumento *arg = new argumento; // Declaro o argumento
    cin >> arg->fin; //leio o tamanho do array
    printf("Digite os valores do array:\n-> ");
    int i;
    for(i=0;i<arg->fin;i++){
        cin >> A[i];
    }
    pthread_t thread;
    arg->fin--; //atualizo os valores do argumento
    arg->ini=0;
    pthread_create(&thread, NULL, merge_sort, (void*)arg); //crio a thread
    //merge_sort(A, 0, An);
    pthread_join(thread, NULL);//espero ela terminar
    cout << "O array ordenado eh:\n-> ";
    for(i=0;i<=arg->fin;i++){
        cout << A[i] << " "; // printo o array ordenado
    }
    cout << endl;
    return 0; // FIM
}