Iterative Merge Sort in C++

The Merge Sort that we've seen before in this blog was a recursive merge sort, but what if you were asked to implement merge sort using iteration. Well, we can implement iterative merge sort very easily using only 2 loops

.

Time Complexity Of Iterative Merge Sort

Time Complexity of iterative merge sort is  O(nLog(n)).

Code For Iterative Merge Sort In C++

#include<iostream>

using namespace std;

#define size 20

void Merge(int arr[] , int low, int mid, int high)

{

        int tempArr[size], tempPos,i,j;

        

        i=tempPos=low;

        j=high;

        while(i<=mid && j <= High)

        {

                if(arr[i] < arr[j])

                {

                        tempArr[tempPos++]=arr[i++];

                }

                else

                {

                        tempArr[tempPos++]=arr[j++];

                }

        }

if(i > mid)

{

        for( int k = j ; k <= high ; k++)

        {

                tempArr[tempPos++] = arr[k];

        }

}

else

{

      for( int k = i ; k <= mid ; k++)

        {

                tempArr[tempPos++] = arr[k];

        }

}

for(int p = low ; p <= high ; p++)

{

    arr[p] = tempArr[p];

}

}

//void merge...

void iterativeMergeSort(int arr[], int n)

{

        int p,i,l,m,h;

        

        for( p = 2 ; p <= n ; p *= 2)

        {

                for( i = 0 ; i + p - 1 <= n ; i += p)

                {

                    l = i;

                    h = i + p + 1;

                    m = ( l + h) / 2;

                    Merge( arr , l , m , h);

                }

        }

    if( p / 2 < n)

    {

            Merge( arr , 0 , p / 2 - 1 , n);

    }

}

// void iterativeMergeSort...

void showArr( int arr[] , int n)

{

        for( int i = 0 ;i < n; i++)

        {

                cout<<arr[i]<<" ";

        }

cout<<endl;

}

// void showArr...

int main()

{

      int arr[] = {3 , 4 , 2 , 5 , 6 , 7 , 1 , 9 , 8};

      int s = sizeof( arr ) / sizeof( *arr );

       

       iterativeMergeSort( arr , s );

       showArr(arr,s);

return 0;

}

//int main...

Output of Iterative Merge Sort Code 

1  2  3  4  5  6  7  8  9