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

#define MIN_SIZE_FOR_THREAD 1000  // Below this, use normal (sequential) merge sort

typedef struct {
    int *arr;
    int left;
    int right;
} Args;

// Standard merge function
void merge(int *arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }

    while (i < n1)
        arr[k++] = L[i++];

    while (j < n2)
        arr[k++] = R[j++];

    free(L);
    free(R);
}

// Simple sequential merge sort (no threads)
void merge_sort_seq(int *arr, int left, int right) {
    if (left >= right) return;

    int mid = (left + right) / 2;
    merge_sort_seq(arr, left, mid);
    merge_sort_seq(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

// Thread function for concurrent merge sort
void *merge_sort_concurrent(void *arg) {
    Args *args = (Args *)arg;
    int left = args->left;
    int right = args->right;
    int *arr = args->arr;

    if (left >= right) {
        free(args);
        return NULL;
    }

    int mid = (left + right) / 2;
    int size = right - left + 1;

    // If segment is large, use threads for left/right halves
    if (size >= MIN_SIZE_FOR_THREAD) {
        pthread_t t1, t2;

        Args *leftArgs = (Args *)malloc(sizeof(Args));
        Args *rightArgs = (Args *)malloc(sizeof(Args));

        leftArgs->arr = arr;
        leftArgs->left = left;
        leftArgs->right = mid;

        rightArgs->arr = arr;
        rightArgs->left = mid + 1;
        rightArgs->right = right;

        // Create threads for left and right halves
        pthread_create(&t1, NULL, merge_sort_concurrent, leftArgs);
        pthread_create(&t2, NULL, merge_sort_concurrent, rightArgs);

        // Wait for both halves to be sorted
        pthread_join(t1, NULL);
        pthread_join(t2, NULL);
    } else {
        // Small segment: do normal merge sort (no thread overhead)
        merge_sort_seq(arr, left, mid);
        merge_sort_seq(arr, mid + 1, right);
    }

    // Merge sorted halves
    merge(arr, left, mid, right);

    free(args);
    return NULL;
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int *arr = (int *)malloc(n * sizeof(int));
    if (!arr) {
        perror("malloc failed");
        return 1;
    }

    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    // Prepare root args and spawn initial thread
    pthread_t t;
    Args *args = (Args *)malloc(sizeof(Args));
    args->arr = arr;
    args->left = 0;
    args->right = n - 1;

    pthread_create(&t, NULL, merge_sort_concurrent, args);
    pthread_join(t, NULL);

    printf("Sorted array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    free(arr);
    return 0;
}