Question

C++ help please

Sort the following list using MERGE sort as discussed in this chapter.
Show the list after each iteration of the outer for loop.

26, 45, 17, 65, 33, 55, 12, 18, 2, 12

Sort the following list using MERGE sort as discussed in this chapter.
Show the list after each iteration of the outer for loop.

36, 55, 17, 35, 63, 85, 12, 48, 3, 66, 15

Answer 1

Code has been executed in C++

#include <iostream>
#include<stdlib.h>
using namespace std;

// Function to merge left and right subarrays
void Merging(int arr[], int x, int y, int z)
{
// Assigning the sizes to Temporary arrays
int n1 = y - x + 1;
int n2 = z - y;
// Temporary arrays
int A[n1], B[n2];

// Storing the elements in the Temporary arrays
for (int l = 0; l < n1; l++)
A[l] = arr[x + l];
for (int r = 0; r < n2; r++)
B[r] = arr[y + 1+ r];

// Transfering the elements in aligned manner back to Temporary arrays
int l = 0;
int r = 0;
int t = x;
while (l < n1 && r < n2)
{
if (A[l] <= B[r]) // In case elements are lesser from right subarray
{
arr[t] = A[l];
l++;
}
else
{
arr[t] = B[r]; // Tranfer the right subarray element to the main array
r++;
}
t++;
}
// Transfering the elements back to Temporary arrays in case any element was left
  
while (l < n1) // In case any element of left subarray was remaining
{   
arr[t] = A[l];
l++;
t++;
}
while (r < n2) // In case any element of right subarray was remaining
{
arr[t] = B[r];
r++;
t++;
}
}
// Function to find minimum of two numbers
int minimal(int p, int q)
{
if(p<q)
return p
else
return q
}
// Merge Sort function to sort the array
void Merge_Sort(int arr[], int n)
{
int count=1; // Intializing the counter
// Merging subarrays from down to top
for (int size=1;size<=n-1;size = 2*size)
{
// Starting from the left subarray index upto the array size
for (int s=0;s<n-1;s+= 2*size)
{
// Trying to reach at end point of left subarray
int v = minimal(s + size-1, n-1);
int u = minimal(s + 2*size-1, n-1);

// Calling merge function
Merging(arr, s, v, u);
}
  
// Printing the Iteration
cout<<"\nIteration "<<count<<": ";
for(int i=0;i<n;i++)
{
// Printing the step by step sorting in each Iteration
cout<<arr[i]<<" ";
}
cout<<"\n";
count++; // Incrementing the counter
}
}
// Main driver function
int main()
{
int arr[80]; // Initializing the array
int n;
cout<<"Enter the size of the array:";
cin>>n;
cout<<"\nEnter the array: ";
for (int i=0; i < n; i++)
cin>>arr[i];
// Calling the merge sort function.
Merge_Sort(arr, n);
cout<<"\nSorted array: ";
// Printing the sorted array.
for (int i=0; i < n; i++)
cout<<arr[i]<<" ";
cout<<"\n";
return 0;
}

Code snapshot:-

Output snapshot:-