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

#define ARRAY_SIZE 8  // Size of the array
#define NUM_THREADS 2  // Number of threads

int array[ARRAY_SIZE];

// Struct for passing data to threads
typedef struct {
    int low;
    int high;
} SortRange;

// Function to merge two halves of an array
void merge(int low, int mid, int high) {
    int n1 = mid - low + 1;
    int n2 = high - mid;
    int left[n1], right[n2];

    // Copy data to temp arrays left[] and right[]
    for (int i = 0; i < n1; i++)
        left[i] = array[low + i];
    for (int j = 0; j < n2; j++)
        right[j] = array[mid + 1 + j];

    // Merge the temp arrays back into array[low..high]
    int i = 0, j = 0, k = low;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            array[k] = left[i];
            i++;
        } else {
            array[k] = right[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of left[], if any
    while (i < n1) {
        array[k] = left[i];
        i++;
        k++;
    }

    // Copy the remaining elements of right[], if any
    while (j < n2) {
        array[k] = right[j];
        j++;
        k++;
    }
}

// Function to be executed by the thread
void *merge_sort_thread(void *arg) {
    SortRange *range = (SortRange *)arg;
    int low = range->low;
    int high = range->high;
    if (low < high) {
        int mid = low + (high - low) / 2;

        // Divide the array into two halves
        SortRange leftRange = {low, mid};
        SortRange rightRange = {mid + 1, high};
        merge_sort_thread(&leftRange);
        merge_sort_thread(&rightRange);

        // Merge the sorted halves
        merge(low, mid, high);
    }

    pthread_exit(NULL);
}

int main() {
    pthread_t threads[NUM_THREADS];
    SortRange ranges[NUM_THREADS];
    int segment_size = ARRAY_SIZE / NUM_THREADS;
    
    // Initialize array with random values
    for (int i = 0; i < ARRAY_SIZE; i++) {
        array[i] = rand() % 100;  // Random numbers between 0 and 99
    }

    // Creating threads for merge sort
    for (int i = 0; i < NUM_THREADS; i++) {
        ranges[i].low = i * segment_size;
        ranges[i].high = (i + 1) * segment_size - 1;
        if (i == NUM_THREADS - 1) {
            ranges[i].high = ARRAY_SIZE - 1; // Adjust the last segment
        }
        pthread_create(&threads[i], NULL, merge_sort_thread, &ranges[i]);
    }

    // Waiting for all threads to finish
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }
    
    // Merge sections of the array sorted by individual threads
    SortRange finalRange = {0, ARRAY_SIZE - 1};
    merge_sort_thread(&finalRange);  // Merge all segments

    // Print the sorted array
    printf("Sorted Array:\n");
    for (int i = 0; i < ARRAY_SIZE; i++) {
       printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}