#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

struct packed_args {
  int * A;
  int N;
};

void merge(int * A, int N)
{
  int m = N/2;
  int * v = (int *) malloc(sizeof(int) * N);
  int i = 0;
  int j = m;
  int k = 0;
  while (i < m && j < N) {
    if (A[i] < A[j]) {
      v[k++] = A[i++];
    } else {
      v[k++] = A[j++];
    }
  }
  while (i < m) {
    v[k++] = A[i++];
  }
  while (j < N) {
    v[k++] = A[j++];
  }
  for (int i = 0; i < N; i++) {
    A[i] = v[i];
  }
  free(v);
  for (int i = 0; i < N; i++) {
    printf("%d ", A[i]);
  }
  printf("\n");
}

void * mergesort(void * args)
{
  struct packed_args *v = (struct packed_args *)args;
  if (v->N <= 1) {
    return NULL;
  }
  struct packed_args v1;
  struct packed_args v2;
  int m = (v->N) / 2; // (*v).N == v->N
  v1.N = m;
  v2.N = v->N - m;
  v1.A = (int *)malloc(sizeof(int) * v1.N);
  v2.A = (int *)malloc(sizeof(int) * v2.N);
  for (int i = 0; i < v->N; i++) {
    if (i < m) {
      v1.A[i] = v->A[i];
    } else {
      v2.A[i - m] = v->A[i];
    }
  }
  pthread_t t1;
  pthread_t t2;
  pthread_create(&t1, NULL, mergesort, &v1);
  pthread_create(&t2, NULL, mergesort, &v2);
  pthread_join(t1, NULL);
  pthread_join(t2, NULL);
  // mergesort(&v1);
  // mergesort(&v2);
  for (int i = 0; i < v->N; i++) {
    if (i < m) {
      v->A[i] = v1.A[i];
    } else {
      v->A[i] = v2.A[i - m];
    }
  }
  merge(v->A, v->N);
  return NULL;
}

int main(int argc, char * argv[])
{
  int A[] = {1, 5, 3, 6, 4, 2};
  int N = 6;
  struct packed_args v;
  v.A = A;
  v.N = N;
  for (int i = 0; i < N; i++) {
    printf("%d ", A[i]);
  }
  printf("\n");
  mergesort(&v);
  return 0;
}