/**
 *  \file parallel-mergesort.cc
 *
 *  \brief Implement your parallel mergesort in this file.
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "sort.hh"

void parallelSort (int N, keytype* A)
{
  /* Lucky you, you get to start from scratch */
  /*omp_set_num_threads(64);*/
  #pragma omp parallel
  #pragma omp master
  pmergeSort(A, N);
}

int binarySearch(keytype x, keytype* A2, int sizeA2){
  int first = 0;
  int last = sizeA2 - 1;
  int mid;
  if(sizeA2 > 0){
    while(first<last){
      mid = (first+last)/2;
      if(x <= A2[mid]){
        last = mid;
      }
      else{
        first = mid + 1;
      }
    }
  }
  return last;
}

void pmerge(keytype* A1, int sizeA1, keytype* A2, int sizeA2, keytype* orig){
  assertIsSorted(sizeA1, A1);
  assertIsSorted(sizeA2, A2);

  int halfA = sizeA1/2;
  keytype x = A1[halfA];
  int k = binarySearch(x, A2, sizeA2);


  keytype* A11 = newCopy(halfA, A1);
  keytype* A12 = newCopy((sizeA1-halfA), A1+halfA);
  keytype* A21 = newCopy(k, A2);
  keytype* A22 = newCopy((sizeA2-k), A2+k);

  #pragma omp task
  pmerge(A11, halfA, A21, k, A1);
  pmerge(A12, (sizeA1-halfA), A22, (sizeA2-k), A2);
  #pragma omp taskwait

  int i = 0;
  int j = 0;
  #pragma omp task
    #pragma omp parallel for shared(A1)
    for(i=0; i < sizeA1; i++){
      orig[i] = A1[i];
    }
    #pragma omp parallel for shared(A2)
    for(j = 0; j < sizeA2; j++){
      orig[j+sizeA1] = A2[j];
    }
  #pragma omp taskwait

  free((keytype *)A11);
  free((keytype *)A12);
  free((keytype *)A21);
  free((keytype *)A22);
}

void pmergeSort(keytype* A, int len){
  if(len <= 1){
    return;
  }
  else{
    int i = 0;
    int q = len/2;
    int qq = len - q;

    keytype* A1, A2;
    #pragma omp task
    A1 = newCopy(q,A);
    A2 = newCopy(qq,A+q);
    #pragma omp taskwait

    /*#pragma omp parallel for shared(A, A1) private (i)
    for(i = p; i < q; i++){
      A1[i] = A[i];
    }
    #pragma omp parallel for shared(A, A2) private (i)
    for(i = q+1; i < N; i++){
      A2[i] = A[i];
    }*/

    #pragma omp task
      pmergeSort(A1, q);
      pmergeSort(A2, qq);
    #pragma omp taskwait

    pmerge(A1, q, A2, qq, A);
    free((keytype *)A1);
    free((keytype *)A2);
  }
}


/* eof */