Question

In this assignment you will implement merge-sort algorithm by creating 2 threads instead of 2 processes. First half of the array will be sorted by thread 1 and the second half by thread 2. When the threads complete their tasks, the main program will merge the half arrays.

You should not waste your time on merge-sort algorithm. Use the merge sort algorithm given below

Languaga is C platform Ubuntu

Answer 1

#include <stdio.h>
#include <pthread.h> // header file in c to use thread in c.
#include <stdlib.h>

#define NOTHREADS 2 // no of threads

int a[] = {14, 18, 15, 12, 13, 16, 7, 1, 4, 9};

typedef struct node {
int i;
int j;
} NODE;

void merge(int i, int j) // function for merging the two array.
{
int mid = (i+j)/2;
int ai = i;
int bi = mid+1;

int newa[j-i+1], newai = 0;

while(ai <= mid && bi <= j) {
if (a[ai] > a[bi])
newa[newai++] = a[bi++];
else
newa[newai++] = a[ai++];
}

while(ai <= mid) {
newa[newai++] = a[ai++];
}

while(bi <= j) {
newa[newai++] = a[bi++];
}

for (ai = 0; ai < (j-i+1) ; ai++)
a[i+ai] = newa[ai];

}

void * mergesort(void *a) // function for merge sort
{
NODE *p = (NODE *)a;
NODE n1, n2;
int mid = (p->i+p->j)/2;
pthread_t thread1, thread2; // declaring the two threads.
int retur;

n1.i = p->i; //n1 for first half of array.
n1.j = mid;

n2.i = mid+1; // n2 for second half of array.
n2.j = p->j;

if (p->i >= p->j) return 0;

retur = pthread_create(&thread1, NULL, mergesort, &n1);
if (retur) {
printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, retur);
exit(1);
}

retur = pthread_create(&thread2, NULL, mergesort, &n2);
if (retur) {
printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, retur);
exit(1);
}

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

merge(p->i, p->j);
pthread_exit(NULL);
}

int main() // main function for calling every function. and showing the final sorted array.
{
int i;
NODE m;
m.i = 0;
m.j = 9;
pthread_t thread;

int retur;

retur=pthread_create(&thread, NULL, mergesort, &m);
if (retur) {
printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, retur);
exit(1);
}

pthread_join(thread, NULL);

for (i = 0; i < 10; i++)
printf ("%d ", a[i]);

printf ("\n");

// pthread_exit(NULL);
return 0;
}

output

input 1 47 9 12 13 14 15 16 18 .. .Program finished with exit code 0 Press ENTER to exit console.