Please help with this merge sort USING C++ and also Compile your code with the G
ID: 3750276 • Letter: P
Question
Please help with this merge sort USING C++ and also
Compile your code with the GNU C++ compiler using the 2011 C++ standard
MergeSort Description Implement the mergesort algorithm for sorting an array of integers. Input structure Each case starts with an integer number which indicates the number of elements to be sorted. Then, the elements follow, one per line. You can assume the input is correctly structured (i.e., no data are missing Output structure Output the sorted sequence separeted by"" (in non-decreasing order). Do not insert spaces or a new line at the beginning or at the end of any element.Explanation / Answer
#include <iostream>
using namespace std;
// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
// We have low to mid and mid+1 to high already sorted.
int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;
// Merge the two parts into temp[].
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
}
// Insert all the remaining values from i to mid into temp[].
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
}
// Insert all the remaining values from j to high into temp[].
while (j <= high)
{
temp[k] = a[j];
k++;
j++;
}
// Assign sorted data stored in temp[] to a[].
for (i = low; i <= high; i++)
{
a[i] = temp[i-low];
}
}
// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
// Split the data into two half.
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
// Merge them to get sorted output.
Merge(a, low, high, mid);
}
}
int main()
{
int n, i;
cout<<" Enter the number of data element to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++)
{
cin>>arr[i];
}
MergeSort(arr, 0, n-1);
// Printing the sorted data.
cout<<" Sorted Data ";
for (i = 0; i < n; i++)
cout<<arr[i]<< ";";
return 0;
}
sample input:
Enter the number of data element to be sorted: 5
3
2
4
5
6
sample output:
Sorted Data 2;3;4;5;6;