#include <math.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define INSERTION_SORT_THRESHOLD 50
#define BLOCKSIZE 256
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b)                                                             \
  {                                                                            \
    a ^= b;                                                                    \
    b ^= a;                                                                    \
    a ^= b;                                                                    \
  }

typedef struct {
  int *array;
  int left;
  int right;
  int depth;
} quicksort_args;

int max_threads;
int current_threads = 1;
pthread_mutex_t thread_lock = PTHREAD_MUTEX_INITIALIZER;

// Insertion sort for small ranges
void insert_sort(int *left, int *right) {
  for (int *pi = left + 1; pi <= right; pi++) {
    if (*pi < *left)
      swap(*pi, *left);
  }
  for (int *pi = left + 2; pi <= right; pi++) {
    int h = *pi;
    int *pj = pi - 1;
    while (h < *pj) {
      *(pj + 1) = *pj;
      pj--;
    }
    *(pj + 1) = h;
  }
}

// Median-of-three
#define sort3fast(a, b, c)                                                     \
  if (b < a) {                                                                 \
    if (c < a) {                                                               \
      if (c < b) {                                                             \
        swap(a, c);                                                            \
      } else {                                                                 \
        int h = a;                                                             \
        a = b;                                                                 \
        b = c;                                                                 \
        c = h;                                                                 \
      }                                                                        \
    } else {                                                                   \
      swap(a, b);                                                              \
    }                                                                          \
  } else {                                                                     \
    if (c < b) {                                                               \
      if (c < a) {                                                             \
        int h = c;                                                             \
        c = b;                                                                 \
        b = a;                                                                 \
        a = h;                                                                 \
      } else {                                                                 \
        swap(b, c);                                                            \
      }                                                                        \
    }                                                                          \
  }

// Hoare’s partition with median-of-three
void partition(int *left0, int *right0, int **l1, int **r1, int **l2,
               int **r2) {

  int *mid = left0 + (right0 - left0) / 2;
  int piv = *mid;
  *mid = *(left0 + 1);
  sort3fast(*left0, piv, *right0);
  *(left0 + 1) = piv;

  int *left = left0 + 1;
  int *right = right0;

  while (1) {
    while (*++left < piv)
      ;
    while (*--right > piv)
      ;
    if (left >= right)
      break;
    swap(*left, *right);
  }

  *(left0 + 1) = *right;
  *right = piv;

  if (right < mid) {
    *l1 = left0;
    *r1 = right - 1;
    *l2 = right + 1;
    *r2 = right0;
  } else {
    *l1 = right + 1;
    *r1 = right0;
    *l2 = left0;
    *r2 = right - 1;
  }
}

// Recursive quicksort, parallelized
void *parallel_quicksort(void *args) {
  quicksort_args *qargs = (quicksort_args *)args;
  int *array = qargs->array;
  int left = qargs->left;
  int right = qargs->right;
  int depth = qargs->depth;

  while (right - left >= INSERTION_SORT_THRESHOLD) {
    int *l, *r, *l2, *r2;
    partition(array + left, array + right, &l, &r, &l2, &r2);
    int l_idx = l - array;
    int r_idx = r - array;
    int l2_idx = l2 - array;
    int r2_idx = r2 - array;

    int spawn = 0;
    pthread_t thread;
    quicksort_args *right_args = malloc(sizeof(quicksort_args));
    right_args->array = array;
    right_args->left = l2_idx;
    right_args->right = r2_idx;
    right_args->depth = depth + 1;

    pthread_mutex_lock(&thread_lock);
    if (current_threads < max_threads) {
      current_threads++;
      spawn = 1;
    }
    pthread_mutex_unlock(&thread_lock);

    if (spawn) {
      pthread_create(&thread, NULL, parallel_quicksort, right_args);
    } else {
      parallel_quicksort(right_args);
      free(right_args);
    }

    quicksort_args left_args = {array, l_idx, r_idx, depth + 1};
    parallel_quicksort(&left_args);

    if (spawn) {
      pthread_join(thread, NULL);
      pthread_mutex_lock(&thread_lock);
      current_threads--;
      pthread_mutex_unlock(&thread_lock);
      free(right_args);
    }

    return NULL;
  }

  // small array — do insertion sort
  insert_sort(array + left, array + right);

  if (depth == 0)
    free(qargs);
  return NULL;
}

int get_named_arg(int argc, char *argv[], const char *name) {
  for (int i = 1; i < argc - 1; ++i) {
    if (strcmp(argv[i], name) == 0) {
      return atoi(argv[i + 1]);
    }
  }
  return -1;
}

int main(int argc, char **argv) {
  int power = get_named_arg(argc, argv, "--size");
  max_threads = get_named_arg(argc, argv, "--threads");

  if (power < 1 || max_threads < 1) {
    fprintf(stderr, "Usage: %s --threads <num> --size <log10(size)>\n",
            argv[0]);
    return EXIT_FAILURE;
  }

  int n = (int)pow(10, power);
  int *array = (int *)malloc(n * sizeof(int));
  if (!array) {
    perror("malloc");
    return EXIT_FAILURE;
  }

  srand(time(NULL));
  for (int i = 0; i < n; i++)
    array[i] = rand();

  quicksort_args *args = malloc(sizeof(quicksort_args));
  args->array = array;
  args->left = 0;
  args->right = n - 1;
  args->depth = 0;

  parallel_quicksort(args);

  free(array);
  return 0;
}