Question

Write code for iterative merge sort algorithm. It is also known as bottom-up merge sort. There should not be any recursive call for this approach. Include your code and screenshot of output with the answer. You can choose any programming language for this problem.

Answer 1

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.