write a C program which performs multithreaded merge sort on a given array. Write it in Linux operating system.

First, an unsorted list of data is divided into as many small partitions as possible. Then these partitions get sorted internally, and merged back together with other partitions to produce the sorted list. Pseudo-code of the algorithm is given as follows:

When programmed tradionally, it is advised to recursively call the given merge() function for each par-tition of the array. In this homework we want to see that recursion is replaced with multithreaded programming; such that new threads must be created for each partition and each thread must be re-sponsible from creating and merging new smaller partitions. Input and output of your program must be printed on screen clearly. Each thread must display their input and output as well.

Hints:

1.use POSIX threads

2. Input array can be speci ed as random numbers generated on runtime or it can be read from les. Do not read input from keyboard. Your input must contain at least 30 integers.

3. You may use semaphores if you nd them necessary for your implementation

Sample Output:

Input: 5 9 1 4 8 7 3 0 2 6

Thread 139754931013376 before: 7 3 0 2 6

Thread 139754922620672 before: 7 3 0

Thread 139754914227968 before: 2 6

Thread 139754939406080 before: 5 9 1 4 8

Thread 139754905835264 before: 7 3

Thread 139754889049856 before: 5 9 1

Thread 139754670647040 before: 7

Thread 139754897442560 before: 2

Thread 139754897442560 after : 2

Thread 139754662254336 before: 6

Thread 139754662254336 after : 6

Thread 139754914227968 after : 2 6

Thread 139754637076224 before: 3

Thread 139754637076224 after : 3

Thread 139754679039744 before: 0

Thread 139754679039744 after : 0

Thread 139754653861632 before: 4 8

Thread 139754662254336 before: 4

Thread 139754662254336 after : 4

Thread 139754645468928 before: 5 9

Thread 139754897442560 before: 8

Thread 139754628683520 before: 1

Thread 139754628683520 after : 1

Thread 139754670647040 after : 7

Thread 139754897442560 after : 8

Thread 139754905835264 after : 3 7

Thread 139754653861632 after : 4 8

Thread 139754922620672 after : 0 3 7

Thread 139754931013376 after : 0 2 3 6 7

Thread 139754662254336 before: 5

Thread 139754662254336 after : 5

Thread 139754410604288 before: 9

Thread 139754410604288 after : 9

Thread 139754645468928 after : 5 9

Thread 139754889049856 after : 1 5 9

Thread 139754939406080 after : 1 4 5 8 9

Output: 0 1 2 3 4 5 6 7 8 9

MERGE-SORT(A, p,r) 1 ifp