Merge soil implementation Please implements the merge sort algorithm and sort al
ID: 3574724 • Letter: M
Question
Merge soil implementation Please implements the merge sort algorithm and sort all data stored in the file sort txt Print the sorted items to show that your program can work correctly. Please prove the complexity of the merge sort algorithm is O(Nlog2 N) using either the mathematic proof or recursion tree. Please indicate if the merge sort you implement is stable How many auxiliary memory spaces are required during the merge sort algorithm? Sort txt 29, 18, 8, 15, 21, 10, 12, 36, 45, 58, 60, 41, 25, 6, 33, 40, 52, 9, 55, 58, 26, 33, 5, 66, 56, 19, 3, 22, 48, 50, 35, 64, 11Explanation / Answer
#include <iostream>
using namespace std;
void merge(int *,int, int , int );
void mergesort(int *ar, int lowest, int highest)
{
int middle;
if (lowestest < highestest)
{
middle=(lowest+highest)/2;
mergesort(ar,lowest,middle); //passing the left of array to be sorted
mergesort(ar,middle+1,highest); //passing the right array to be sorted
merge(ar,lowest,highest,middle); // function to merge arrays
}
return;
}
void merge(int *arr, int lowest, int highest, int middle)
{
int p, q, r, temp[50];
p = lowest;
r = lowest;
q = middle + 1;
while (p <= middle && q <= highest)
{
if (arr[p] < arr[q])
{
temp[r] = arr[p];
r++;
p++;
}
else
{
temp[r] = arr[q];
r++;
q++;
}
}
while (p<= middle)
{
temp[r] = arr[p];
r++;
p++;
}
while (q <= highest)
{
temp[r] = arr[q];
r++;
q++;
}
for (p = lowest; p< r; p++)
{
arr[p] = temp[p];
}
}
int main()
{
int arr[40] ={29,18,8,15,21,10,12,36,45,58,60,41,25,6,33,40,52,9,55,58,26,33,5,66,56,19,3,22,48,50,35,64,11};
int m;
cout<<"enter the elements ";
mergesort(arr, 0, 32);
cout<<"sorted array ";
for (m = 0; m < 32; m++)
{
cout<<arr[m];
}
}