The following function sorts the elements of an array A[n] in place using a recu

Question

The following function sorts the elements of an array A[n] in place using a recursive two-way merge-sort.

Assume that the function merge() merges the two subranges A[ lo, mid] and A[ mid + 1, hi ] of the array A.

void mergesort ( int A[ ], int lo , int hi) { int mid; if( lo < hi ) { mid = ( lo + hi ) / 2 ; mergesort ( A, lo , mid ) ; mergesort ( A, mid+1 , hi); merge( A, lo, mid, mid + 1, hi); } }

Re-Write the function using fork, join, quit such that the two invokations of mergesort ( ) are executed in parallel.

Explanation / Answer

#include <iostream>
using namespace std;
//Prototype declaration for Merge function
void myMerge(int *, int *, int, int, int);
void mergeSort(int *m, int *n, int l, int h)
{
//l for low and h for high
int p;
if (l < h)
{
p = (l + h)/2;
//Recursive call of mergeSort function
mergeSort(m, n, l, p);
mergeSort(m, n, p + 1, h);
myMerge(m, n, l, p, h);
}
}
//Merge function
void myMerge(int *f, int *s, int lo, int p, int hi)
{
int h, i, j, k;
h = lo;
i = lo;
j = p + 1;

while ((h <= p) && (j <= hi)) // Traverse both halves of the array
{
if (f[h] <= f[j]) // if an element of left half is less than element of right half
{
s[i] = f[h]; // store element of left half in the temporary array
h++; // shift the index of the array from which the element was copied to temporary
}
else // otherwise store the element of the right half in the temporary array
{
s[i] = f[j];
j++; // shift the index of the array from which the element was copied to temporary
}
i++;
}
if (h > p) // If traversal of left half is done,
// copy remaining elements from right half to temporary
{
for (k = j; k <= hi; k++)
{
s[i] = f[k];
i++;
}
}
else // otherwise copy remaining elements from left half to temporary
{
for (k = h; k <= p; k++)
{
s[i] = f[k];
i++;
}
}
for (k = lo; k <= hi; k++)
f[k] = s[k]; // recopy the values from temporary to original array.
}

int main()
{
int no;
cout<<" Enter the size: ";
cin>>no;
int a[no];
cout<<" Enter "<<no<<" data ";
for(int c = 0; c < no; c++)
cin>>a[c];
int num;
//Calculates the number of elements
num = sizeof(a)/sizeof(int);

int temp[num]; // temporary array to be used for merging

mergeSort(a, temp, 0, num-1);

cout<<" After Sorting "<<endl;

for (int i = 0; i < num; i++)
cout << a[i] << " ";
cout << endl;
}

Output 1:

Enter the size: 5

Enter 5 data
22
-8
56
99
-44

After Sorting:
-44 -8 22 56 99

Output 2:

Enter the size: 8

Enter 8 data
22
-55
36
-2
56
99
45
65

After Sorting
-55 -2 22 36 45 56 65 99

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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