Write a multithreaded sorting program in C++ that works as follows: A list of in

Question

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 thread – a “merging thread” – which merges 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. Graphically, this program is structures according to the following Figure. This programming project will require passing parameters to each of the sorting threads. In particular, it will be necessary to identify the starting index from which each thread is to begin sorting. The parent thread will output the sorted array once all sorting threads have exited.

Explanation / Answer

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

struct idx{int p,r;};

void* mrg_srt(void* prm){
struct idx* pr = (struct idx*) prm;
int p = pr->p, r = pr->r , ret1,ret2;
if (p==r)
pthread_exit(0);

pthread_t thread1,thread2;
struct idx 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,mrg_srt,(void*) &pr1);
if (ret1>0)
printf("failed to create new thread 1 ");

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

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;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.