Multithreaded Merge Sort

another post about posix threads, we implement the merge sort using threads

  1. divide the array into 2 halves
  2. call merge_sort on both sub array each call in a thread
  3. wait for the threads to finish (using join)
  4. merge the 2 arrays

here i’ve used an array (b) of the same size of a (pre-created array)┬áto avoid allocating new space at each merge call.

BTW using the thread doesn’t improve time complexity, this implementation is nlog(n). If you are interested in a better multi-threaded algorithm refer Introduction to Algorithms – Cormen.

also the code is on github


int* a;
int* b; //sorted array
int n;

struct index{int p,r;};

void* merge_sort(void* param){
    struct index* pr = (struct index*) param;
    int p = pr->p,  r = pr->r , ret1,ret2;
    if (p==r)
        pthread_exit(0);

    pthread_t thread1,thread2;
    struct index pr1,pr2;
    int q = (p+r)/2;
    pr1.p = p;    pr1.r = q;
    pr2.p = q+1;  pr2.r = r;

    ret1 = pthread_create(&thread1,NULL,merge_sort,(void*) &pr1);
    if (ret1>0)
        printf("failed to create new thread 1\n");

    ret2 = pthread_create(&thread2,NULL,merge_sort,(void*) &pr2);
    if (ret2>0)
        printf("failed to create new thread 2\n");

    pthread_join(thread1,NULL);
    pthread_join(thread2,NULL);

    int k = p ,i = p ,j = q+1;

    while (i<=q && j<=r){
        if (a[i] < a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    for (; i<=q ; i++)
        b[k++] = a[i];
    for (; j<=r ; j++)
        b[k++] = a[j];

    for (i= p ; i <= r ;i++)
        a[i] = b[i];

    pthread_exit(0);
    return NULL;
}