mergeSort algorithm with fewer global variables

The key to remove global variable is to locally pass data from functions to functions. First of all, pthread_create have a parameter called arg which enable you to pass a structure with many fields in argument to the created thread. The idea is to declare a structure like this:

// TODO: check all the fields are actually needed
struct ThreadContext
{
    pthread_mutex_t mutex_p;
    pthread_mutex_t mutex_pi;

    int MAX;        // number of elements in the array
    int THREAD_MAX; // number of threads
    int idx[20];    // hold the right end at each vector subdivision
    int p_i = 0;

    int *a;
    int part = 0;
};

Then create it on the stack, then fill it (typically the mutex fields), before creating threads, and finally pass it to the threads using:

// &your_struct is a pointer to your_struct
pthread_create(&threads[i], NULL, mergeSort, (void*)&your_struct);

Your mergeSort function can then extract the data structure from the void* pointer.

void* mergeSort(void* arg)
{
    struct ThreadContext* context = (struct ThreadContext*)arg;

    pthread_mutex_lock(&context.mutex_p); // Example of usage
    // [...]
}

You can also add new parameters to the merge and merge_sort functions if needed.

Note that int idx[20]; can be replaced by int* idx and allocated dynamically (using malloc and free) so not to have a predetermined limit to the number of threads that can be used in your program.

I am surprised to see mutexes in a merge sort. Indeed, the idea of a parallel merge sort is to split the work between thread so each work on different data. As a result, there is no need for critical sections. You can use the thread ID to select with thread do the merge instead of preventing other threads to do operations with critical sections.

Note that you can create an array of ThreadContext and fill it with different data so each thread have different information (filled by the main thread). For example, the thread ID can be different as well as the start/stop indices. This help you not to use any mutexes in your code. To avoid the replication of some fields in each thread you can even split the structure into 3 different structures:

struct SharedContext
{
    // Shared fields like the number of threads, the array pointer, the total number of element, mutexes (if any), etc.
};

struct PrivateContext
{
    // Thread private fields like the thread ID, the start/stop indices, etc.
};

struct ThreadContext
{
    struct SharedContext* sharedCtx;
    struct PrivateContext privateCtx;
};

Note that sharedCtx should be filled with the pointer to a SharedContext structure created by the main thread (eg. allocated on the stack).

You can remove the global variables by passing the appropriate arguments to each thread.

For this, you can define an array of structures, one for each thread, populate it with arguments before launching the thread and pass the structure pointer to pthread_create.

With each thread acting on its own data, you no longer need the global variables, nor even the mutexes.

Here is a modified version:

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

struct thread_data {
    int *a;
    int low;
    int high;
};

// mergeSort function to interclass two parts
void merge(int *a, int lo, int mid, int hi) {
    int count = hi - lo;
    int sorted[count];
    int i = lo, k = mid, m = 0;
    while (i < mid && k < hi) {
        if (a[i] <= a[k])
            sorted[m++] = a[i++];
        else
            sorted[m++] = a[k++];
    }
    while (i < mid)
        sorted[m++] = a[i++];

    for (i = 0; i < m; i++)
        a[lo + i] = sorted[i];
}

// mergeSort function
void merge_sort(int *a, int low, int high) {
    // calculates the middle of the array
    int mid = low + (high - low) / 2;
    if (high - low > 1) {
        // I call the first half
        merge_sort(a, low, mid);

        // I call the second half
        merge_sort(a, mid, high);

        // interclassification between the two halves
        merge(a, low, mid, high);
    }
}

// thread function for multi-threading
void *mergeSort(void *arg) {
    struct thread_data *data = arg;
    merge_sort(data->a, data->low, data->high);
    return NULL;
}

void isSorted(const int *a, int len) {
    for (int i = 1; i < len; i++) {
        if (a[i] < a[i - 1]) {
            printf("Sorting is not complete\n");
            return;
        }
    }
    printf("Sorting completed\n");
}

void printArray(const int *a, int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// The main program
int main() {
    int *a;         // array pointer
    int MAX;        // number of elements in the array
    int THREAD_MAX; // number of threads

    printf("Enter the number of items in the array:");
    if (scanf("%d", &MAX) != 1)
        return 1;

    printf("Enter the number of threads you want:");
    if (scanf("%d", &THREAD_MAX) != 1)
        return 1;

    // generates random number in array up to 1000
    a = malloc(MAX * sizeof(int));
    srand(time(NULL));
    for (int i = 0; i < MAX; i++) {
        a[i] = rand() % 1000;
    }

    // t1 and t2 to calculate the time to mergeSort
    clock_t t1 = clock();

    // thread creation
    pthread_t threads[THREAD_MAX];
    struct thread_data data[THREAD_MAX];

    for (int i = 0; i < THREAD_MAX; i++) {
        data[i].a = a;
        data[i].low = i * MAX / THREAD_MAX;
        data[i].high = (i + 1) * MAX / THREAD_MAX;
        pthread_create(&threads[i], NULL, mergeSort, &data[i]);
    }

    // joining all threads
    for (int i = 0; i < THREAD_MAX; i++) {
        pthread_join(threads[i], NULL);
    }

    // merging on the last elements
    // this merge phase is inefficient
    for (int i = 1; i < THREAD_MAX; i++) {
        int mid = data[i].low;
        int high = data[i].high;
        merge(a, 0, mid, high);
    }

    clock_t t2 = clock();
    printf("Time required: %f\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
    isSorted(a, MAX);

    //sorted array display
    if (MAX < 100) {
        printf("Sorted array: ");
        printArray(a, MAX);
    }
    free(a);

    return 0;
}