merge-sort-pthreads.c

#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;
}

This program uses pthreads to parallelize the merge sort algorithm. It divides the array into segments and uses multiple threads to sort these segments simultaneously. Finally, it merges the sorted segments to form a fully sorted array.

Array Initialization: The array is filled with random numbers, providing a range of values to sort.

Thread Function (merge_sort_thread): Each thread executes this function, which performs the merge sort algorithm on a specific segment of the array. The function divides its segment into smaller parts, sorts these parts, and then merges them. The sorting and merging are done recursively within each segment.

Main Function: It divides the array into equal-sized segments and creates a thread for each segment. Each thread sorts its assigned segment. The main function then waits for all threads to complete their sorting tasks.

Merging Sorted Segments: After all threads have finished sorting their segments, the main function performs a final merge. This step combines the sorted segments into a single sorted array.

Final Output: The program prints the sorted array, showcasing the result of the parallel merge sort operation.

This implementation of parallel merge sort is efficient for large arrays. By dividing the array and sorting segments in parallel, the algorithm reduces the total sorting time.

This approach is particularly effective on multi-core processors, where each thread can run on a separate core, further enhancing the sorting speed.
The final merging step ensures that the entire array is sorted correctly, maintaining the integrity of the merge sort algorithm.