the following function sorts the elements of an array An in

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)

mergesort(A, lo, mid, mid+1, hi)

}

}

Solution

#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