Answer:
Here is the C++ program:
#include <iostream> // for using input output functions
using namespace std; // to identify objects as cin cout
void merge(int array[], int left, int mid, int right);
// to merge the array into two parts i.e. from left to mid and mid+1 to right
int minimum(int a, int b) { return (a<b)? a :b; }
//to find the minimum of the 2 values
void IterativeMergeSort(int array[], int num) { //function to sort the array
int size; //determines current size of subarrays
int left; //to determine the start position of left subarray
//to merge the sub arrays using bottom up approach
for (size=1; size<=num-1; size = 2*size) {
//to select start position of different subarrays of current size
for (left=0; left<num-1; left += 2*size) {
// To determine the end point of left sub array and start position of right //which is mid+1
int mid = minimum(left + size - 1, num-1);
int right = minimum(left + 2*size - 1, num-1);
// Merge the sub arrays from left to mid and mid+1 to right
merge(array, left, mid, right); } } }
// function to merge the array into two parts i.e. from left to mid and mid+1 //to right
void merge(int array[], int left, int mid, int right){
int i, j, k; // variables to point to different indices of the array
int number1 = mid - left + 1;
int number2 = right - mid;
//creates two auxiliary arrays LEFT and RIGHT
int LEFT[number1], RIGHT[number2];
//copies this mid - left + 1 portion to LEFT array
for (i = 0; i < number1; i++)
LEFT[i] = array[left + i];
//copies this right - mid portion to RIGHT array
for (j = 0; j < number2; j++)
RIGHT[j] = array[mid + 1+ j];
i = 0;
j = 0;
k = left;
//merge the RIGHT and LEFT arrays back to array from left to right i.e //arr[left...right]
while (i < number1 && j < number2) {
if (LEFT[i] <= RIGHT[j])
/*checks if the element at i-th index of LEFT array is less than or equals to that of j-th index of RIGHT array */
{ array[k] = LEFT[i];
//if above condition is true then copies the k-th part of array[] to LEFT //temporary array
i++; }
else //when the above if condition is false
{ array[k] = RIGHT[j];
//moves k-th part of array[] to j-th position of RIGHT temporary array
j++; }
k++; }
while (i < number1) { //copies remaining elements of LEFT array
array[k] = LEFT[i];
i++;
k++; }
while (j < number2) { //copies remaining elements of RIGHT array
array[k] = RIGHT[j];
j++;
k++; } }
int main() {
int Array[] = {9, 18, 15, 6, 8, 3}; // an array to be sorted
int s = sizeof(Array)/sizeof(Array[0]);
//sizeof() is used to return size of array
cout<<"Input array: ";
int i;
for (i=0; i < s; i++) //to print the elements of given array
cout<<Array[i]<<" ";
cout<<endl;
IterativeMergeSort(Array, s); //calls IterativeMergeSort() function
cout<<"Sorted array after applying Iterative Merge Sort:"<<endl;
for (i=0; i < s; i++) //to print the elements of the sorted array
cout<<Array[i]<<" "; }
Explanation:
The program is well explained in the comments mentioned above with each line of the code. The screenshot of the program along with its output is attached.
