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

// Global array to be sorted
int arr[] = {7, 12, 19, 3, 18, 4, 2, 6, 15, 8}; 
int sorted_arr[10]; // To store the final sorted result

// Function for Bubble Sort on a specified range of the array
void bubbleSort(int *array, int start, int end) {
    // Bubble sort for sorting the array between start and end indices
    for (int i = start; i < end - 1; i++) {
        for (int j = start; j < end - i - 1 + start; j++) {
            // If the current element is greater than the next, swap them
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

// Thread function for sorting a specific range of the array
void *sortThread(void *arg) {
    // Cast the argument back to an integer array containing the start and end indices
    int *indices = (int *)arg;
    int start = indices[0];
    int end = indices[1];

    // Call the bubbleSort function on the specified range
    bubbleSort(arr, start, end);
    return NULL;
}

// Merge function to merge two sorted subarrays into the final sorted array
void *mergeThread(void *arg) {
    int size = 10;          // Size of the original array
    int mid = size / 2;     // Mid-point for splitting the array
    int i = 0, j = mid, k = 0;

    // Merge the two sorted halves into the sorted_arr
    while (i < mid && j < size) {
        if (arr[i] < arr[j]) {
            sorted_arr[k++] = arr[i++];  // Copy the smaller element from the first half
        } else {
            sorted_arr[k++] = arr[j++];  // Copy the smaller element from the second half
        }
    }

    // If there are any remaining elements in the first half, add them
    while (i < mid) {
        sorted_arr[k++] = arr[i++];
    }

    // If there are any remaining elements in the second half, add them
    while (j < size) {
        sorted_arr[k++] = arr[j++];
    }

    return NULL;
}

int main() {
    int size = 10;  // Size of the array
    pthread_t thread1, thread2, mergeThreadID;

    // Define the indices for the two halves of the array
    int indices1[2] = {0, size / 2};      // First half of the array
    int indices2[2] = {size / 2, size};   // Second half of the array

    // Create two threads to sort the two halves of the array concurrently
    pthread_create(&thread1, NULL, sortThread, (void *)indices1); // Sort the first half
    pthread_create(&thread2, NULL, sortThread, (void *)indices2); // Sort the second half

    // Wait for both sorting threads to finish
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    // Create a thread to merge the two sorted halves into a final sorted array
    pthread_create(&mergeThreadID, NULL, mergeThread, NULL);
    pthread_join(mergeThreadID, NULL);  // Wait for the merge thread to finish

    // Print the final sorted array
    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", sorted_arr[i]);  // Output each element of the sorted array
    }
    printf("\n");

    return 0;  // Return successful execution
}