Write a multithreaded sorting program in C that works as follows: A list of integers is divided into two smaller lists of equal size. Two separate threads (which we will term sorting threads) sort each sublist using a sorting algorithm of your choice. The two sublists are then merged by a third threada merging threadwhich merges the two sublists into a single sorted list. Because global data are shared cross all threads, perhaps the easiest way to set up the data is to create a global array. Each sorting thread will work on one half of this array. A second global array of the same size as the unsorted

integer array will also be established. The merging thread will then merge the two sublists into this second array.

The list of integers to be sorted is (use the exact values and order provided below): {7, 12, 19, 3, 18, 4, 2, -5, 6, 15, 8}

Hints: 1) The parent thread initializes an unsorted array with integer numbers. The easiest approach for sharing data is to create global data. For example, at file scope:

#define SIZE ( sizeof(list)/sizeof(*list) )

int list[] = {7, 12, 19, 3, 18, 4, 2, -5, 6, 15, 8}; // array initially filled with unsorted numbers

int result[SIZE] = {0}; // same contents as unsortedarray, but sorted

2) The parent thread then creates sorter threads, passing each a parameter containing the location (pointer) and size (unsigned int) of the unsorted array. The easiest approach for passing data to threads is to create a data structure using a typedef and struct. For example,

/* structures for passing data to worker threads */

typedef struct

{ int * subArray;

unsigned int size; } SortingThreadParameters;

typedef struct

{ SortingThreadParameters left;

SortingThreadParameters right;

} MergingThreadParameters;

3) The parent creates worker threads using a strategy similar to:

SortingThreadParameters * paramsLeft = malloc( sizeof( SortingThreadParameters ) );

paramsLeft->subArray = list;

paramsLeft->size = SIZE/2;

SortingThreadParameters * paramsRight = malloc( sizeof( SortingThreadParameters ) );

paramsRight->subArray = list + paramsLeft->size;

paramsRight->size = SIZE - paramsLeft->size;

MergingThreadParameters * paramsMerge = malloc( sizeof( MergingThreadParameters ) );

paramsMerge->left = *paramsLeft;

paramsMerge->right = *paramsRight;

4) The pointer-to-parameter (e.g. paramsLeft, paramsRight, and paramsMerge) is passed to the pthread_create() function, which in turn is passed as a parameter to the function that is to run as a separate thread.

5) The sorting threads perform an in-place sort. The merging thread does not.