Please help with merge sort with threading!!!! Please use comments in your code, thank you in advance.

These files are a simple implementation of a parallel merge sort using pthreads. The implementation of the merge sort is in par_merge.c, and the code to test it is in test_sort.c. Look at the Makefile. If you type make, the code will be compiled and tested.

Your job is to rewrite function pmerge_sort in file par_merge.c. Please do the following:

1. Read the code to understand how it works. If you do know how merge sort works, look online or in your algorithms book. Its an elegant recursive sorting algorithm and suitable for a concurrent implementations.

2. Look at function pmerge_sort carefully. It creates two threads, each of which sorts half the data. Then the results from these two sorts are merged.

3. Function pmerge_sort creates two threads, but this is wasteful, because pmerge_sort could sort half the data itself, and create only one new thread to sort the other half.

I want you to modify function pmerge_sort so that it creates only one new thread, not two. Do not modify any code except for pmerge_sort! Also, do not modify the arguments or return type of pmerge_sort.

This code is simplistic in that it will create many threads if the input array is large. Dont try running your code on very large inputs. A more realistic algorithm would use the number of available cores as a parameter, and not create more threads than the number of cores.

Here are the files you'll need:

par_merge.c:

/*

* A parallel merge sort using pthreads

*/

#include

#include

#include

#include

#include

typedef struct sort_args_t {

float *x; // array to be sorted

int len; // length of array

} Sort_args;

// sort and return float array x, of length n

// using gnome sort

float *gsort(float *x, int n) {

int i = 0;

while (i < n) {

if (i == 0 || x[i] >= x[i-1]) {

i++;

} else {

// swap x[i] and x[i-1]

float temp = x[i];

x[i] = x[i-1];

x[i-1] = temp;

i--;

}

}

return x;

}

// return a new array obtained by merging arrays

// x and y, where m is the length of x and n

// is the length of y. The input arrays are

// assumed to be sorted. If they are, the output

// will be sorted.

float *merge(float *x, int m, float *y, int n) {

// x and y are merged into new array z

float *z = (float *)malloc((m + n)*(sizeof(float)));

int i = 0; // index into x

int j = 0; // index into y

int k = 0; // index into z

while (i < m || j < n) {

// pick the x element if there are no more y's, or

// if there are x's and y's and the x value is smaller

if (j == n || (i < m && x[i] < y[j])) {

z[k] = x[i];

i++;

} else {

z[k] = y[j];

j++;

}

k++;

}

return z;

}

// sort and return float array x, of length n

// using merge sort

void *pmerge_sort(void *args) {

// unpack arguments

Sort_args *sargs = (Sort_args *)args;

float *x = sargs->x;

int n = sargs->len;

// if n < k, the array is sorted directly

// using another sort algorithm

int k = 100;

if (n < k) {

return(gsort(x, n));

}

// create 2 threads; each sorts half the data

int m = ((float)n)/2.0;

// pack arguments to recursive call

Sort_args args1, args2;

args1.x = x;

args1.len = m;

args2.x = &x[m];

args2.len = n-m;

int rc;

pthread_t p1, p2;

rc = pthread_create(&p1, NULL, pmerge_sort, (void *)&args1); assert(rc == 0);

rc = pthread_create(&p2, NULL, pmerge_sort, (void *)&args2); assert(rc == 0);

// merge the results from the threads

float *x1, *x2;

pthread_join(p1, (void **) &x1);

pthread_join(p2, (void **) &x2);

float *y = merge(x1, m, x2, n-m);

// copy the result back to x and free y

memcpy((void *)x, (void *)y, n*sizeof(float));

free(y);

return (void *)x;

}

// sort array x

void merge_sort(float *x, int n) {

// call recursive helper function

Sort_args args;

args.x = x;

args.len = n;

pmerge_sort((void *)&args);

}

test_sort.c:

/* * Test a sort algorithm for correctness */

#include #include #include #include #include "merge_sort.h"

// test merge sort int main() { // size of test data array int n = 10000;

// initialize input float *x = (float *)malloc(n * sizeof(float)); int i; for (i = 0; i < n; i++) { x[i] = drand48(); }

merge_sort(x, n);

// check the output for correctness float last = -1.0; for (i = 0; i < n; i++) { if (x[i] < last) { printf("sort error at element %d ", i); exit(1); } last = x[i]; } printf("output was sorted correctly ");

return 0; }

merge_sort.h:

void merge_sort(float *, int);

Makefile:

test: pmsort

./pmsort

pmsort: par_merge.c test_sort.c merge_sort.h

gcc -o pmsort test_sort.c par_merge.c -pthread -Wall

clean:

rm -f pmsort *~