Question

Write a program that performs a merge-sort algorithm without using a recursion.

c++ programming language(Only #inlclude <iostream>)

Answer 1

#include<iostream>
using namespace std;
#define MAX 30

int main()
{
        int arr[MAX],temp[MAX],i,j,k,n,size,l1,h1,l2,h2;

        cout<<"Enter the number of elements : "; // To accept number of elements from user
        cin>>n;
  cout<<"\nEnter the elements:\n";
        for(i=0;i<n;i++) //To accept elements to be sorted
        {
                cin>>arr[i];
        }


        /*l1 lower bound of first pair and so on*/
        for(size=1; size < n; size=size*2 )
        {
                l1=0;
                k=0;  //Index for temp array
                while( l1+size < n)
                {
                        h1=l1+size-1;
                        l2=h1+1;
                        h2=l2+size-1;
                        // h2 exceeds the limlt of arr
                        if( h2>=n ) 
                                h2=n-1;
                        
                        /*Merge the two pairs with lower limits l1 and l2*/
                        i=l1;
                        j=l2;
                        
                        while(i<=h1 && j<=h2 )
                        {
                                if( arr[i] <= arr[j] )
                                        temp[k++]=arr[i++];
                                else
                                        temp[k++]=arr[j++];
                        }
                        
                        while(i<=h1)
                                temp[k++]=arr[i++];
                        while(j<=h2)
                                temp[k++]=arr[j++];
                        //Merging complete
                        /*Take the next two pairs for merging */
                        l1=h2+1; 
                }//End of while

                //any pair left
                for(i=l1; k<n; i++) 
                        temp[k++]=arr[i];

                for(i=0;i<n;i++)
                        arr[i]=temp[i];

                
        }//End of for loop
        //Displaying the sorted elements
        cout<<"\nSorted list is :\n";
        for( i = 0 ; i<n ; i++)
                cout<<arr[i]<<" ";
}

Output screenshot:-