SO P&T - 5

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/types.h>

#define MAXN 100005
#define THMAX 5
#define min(x, y) (x <= y ? x : y)

//array que vai ser ordenado
int arr[MAXN];

//mutex para tratar de regios criticas
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
int flag = 0;

//pilha de threads disponiveis atualmente
int stack[THMAX], top;

typedef struct{
    int a, b, x, y, idx;
}merge_range;

void* merge(void* data){
    //Pego os intervalos em que eu vou juntar (merge)
    merge_range *args = data;
    int l = args-> a, r = args->b, i = args->x, j = args->y;
    int val = args -> idx;

    //Variaveis auxiliares
    int ord[MAXN], k, li = l, ls = j;

    //merge
    for(k = l; l <= r && i <= j; k++){
        if(arr[l] <= arr[i]) ord[k] = arr[l++];
        else ord[k] = arr[i++];
    }
    while(l <= r) ord[k++] = arr[l++];
    while(i <= j) ord[k++] = arr[i++];

    //atualizo meu array
    for(; li <= ls; li++) arr[li] = ord[li];

    //região critica (variavel global), atualizo minha pilha de threads disponiveis
    pthread_mutex_lock(&mtx);
    stack[++top] = val;
    pthread_mutex_unlock(&mtx);
    return NULL;
}

void merge_sort(int n){
    //variaveis auxiliares
    int i, j, qtd = 0, aux;
    //threads
    pthread_t thr[THMAX];
    //array que vai guardar a task de cada thread em um instante da execução
    merge_range tmp[THMAX];

    //Inicializo minha pilha de threads
    for(i = 0; i < THMAX; i++) stack[i] = i;
    top = THMAX - 1;

    for(i = 1; i <= n; i <<= 1){
        for(j = 0; j + i <= n; j += (i << 1)  ){
            //enquanto eu nao tiver threads disponiveis não faço nada
            while(top < 0);
            //Pego o indice da proxima thread disponivel
            aux = stack[top];
            //Inicializo os ranges que a thread ficara responsavel em dar o merge
            tmp[ aux ].a = j; tmp[ aux ].b = j + i - 1;
            tmp[ aux ].x = min(tmp[ aux ].b + 1, n - 1); tmp[aux].y = min(tmp[aux].x + i - 1, n - 1);
            //Guardo o seu indice para ser recolado na pilha
            tmp[aux].idx = stack[aux];

            //O trabalho começa
            pthread_create( &thr[ aux ], NULL, &merge, &tmp[aux]);
            pthread_join(thr[ stack[top--] ], NULL);

         }
         //Enquanto todas as threads nao tiverem terminado seu trabalho, eu espero
         while(top != THMAX - 1);
    }
}

int main(){
    //Entrada e saida por arquivo
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    //Tamanho do meu array
    int n;
    scanf("%d", &n);

    //Entrada dos elementos do array
    int i;
    for(i = 0; i < n; i++){
        scanf("%d", arr + i);
    }

    //MERGE SORT
    merge_sort(n);

    //Printando array ordenado
    for(i = 0; i < n; i++){
        printf("%d ", arr[i]);
    }
    putchar('\n');
}