Iterative Merge Sort

When it comes to coding interview prep for software developers or engineers, sorting algorithms is a topic you cannot afford to miss. Problems based on sorting algorithms regularly feature in tech interviews at FAANG and other tier-1 tech companies. In this article, we’ll help you review the iterative merge sort. Here’s what we will cover:

• What Is Iterative Merge Sort?
• How Does Iterative Merge Sort Work?
• Iterative Merge Sort Algorithm
• Recursive Merge Sort Code
• Iterative Merge Sort Code
• Iterative Merge Sort Complexities
• Advantages of Iterative Merge Sort
• Disadvantages of Iterative Merge Sort
• FAQs on Iterative Merge Sort

What Is Iterative Merge Sort?

In Iterative merge sort, we implement merge sort in a bottom-up manner. This is how it works:

1. We start by sorting all sub-arrays of length 1
2. Then, we sort all sub-arrays of length 2 by merging length-1 sub-arrays
3. Then, we sort all sub-arrays of length 4 by merging length-2 sub-arrays
4. We repeat the above step for sub-arrays of lengths 8, 16, 32, and so on until the whole array is sorted

How Does Iterative Merge Sort Work?

Let’s assume that the array Arr[] = {3, 2, 1, 9, 5, 4, 10, 11} of size N = 8 is to be sorted.

Arrays of length 1 are trivially sorted. First, we take sub_size = 1 and merge all pairs of sub-arrays of size 1.

Then, we multiply sub_size by 2, and sub_size becomes 2. Now, we merge all pairs of sub-arrays of size 2.

Again, we multiply sub_size by 2, and sub_size becomes 4, and we merge all pairs of sub-arrays of size 4.

Now, we stop, as sub_size is >= N and the array is sorted.

Iterative Merge Sort Algorithm

Consider an array Arr[] of size N that we want to sort:

Step 1: Initialize sub_size with 1 and multiply it by 2 as long as it is less than N. And for each sub_size, do the following:

Step 2: Initialize L with 0 and add 2*sub_size as long as it is less than N. Calculate Mid as min(L + sub_size – 1, N-1) and R as min(L + (2* sub_size) -1, N-1) and do the following:

Step 3: Copy sub-array [L, Mid-1] in list A and sub-array [Mid, R] in list B and merge these sorted lists to make a sorted list C using the following method:

Step 3.1: Compare the first elements of lists A and B and remove the first element from the list whose first element is smaller and append it to C. Repeat this until either list A or B becomes empty.

Step 3.2: Copy the list(A or B), which is not empty, to C.

Step 4: Copy list C to Arr[] from index L to R.

Recursive Merge Sort Implementation

Here’s the implementation of recursive merge sort algorithm in C++:

#include<bits/stdc++.h>

using namespace std;

void merge(int Arr[], int l, int m, int r) {

   int i, j, k;

   int n1 = m – l + 1;

   int n2 = r – m;

   int L[n1], R[n2];

   for (i = 0; i < n1; i++)

      L[i] = Arr[l + i];

   for (j = 0; j < n2; j++)

      R[j] = Arr[m + 1 + j];

   i = 0, j = 0, k = l;

   while (i < n1 && j < n2) {

      if (L[i] <= R[j]) {

         Arr[k] = L[i];

         i++;

      } else {

         Arr[k] = R[j];

         j++;

      }

      k++;

   }

   while (i < n1) {

      Arr[k] = L[i];

      i++;

      k++;

   }

   while (j < n2) {

      Arr[k] = R[j];

      j++;

      k++;

   }

}

void merge_sort(int L, int R, int Arr[]){

    if(L==R)

        return ;

    int Mid= (L+R)/2;

    // Dividing sub-array from L to R into

    // two parts and recursively solving

    merge_sort(L, Mid, Arr);

    merge_sort(Mid+1, R, Arr);

    // merging two sorted sub-arrays

    merge(Arr,L, Mid, R);

}

int main()

{

    int i;

    int N = 8;

    int Arr[N] = {3, 2, 1, 9, 5, 4, 10, 11};

    cout<<“Unsorted Array: “;

    for(i=0;i<N;i++)

        cout<<Arr[i]<<” “;

    cout<<endl;

    merge_sort(0, N-1, Arr);

    cout<<“Sorted Array: “;

    for(i=0;i<N;i++)

        cout<<Arr[i]<<” “;

    return 0;

}

Output:

Unsorted Array: 3 2 1 9 5 4 10 11

Sorted Array: 1 2 3 4 5 9 10 11

Iterative Merge Sort Implementation

And this is how iterative merge sort can be implemented in C++:

#include<bits/stdc++.h>

using namespace std;

void merge(int Arr[], int l, int m, int r) {

   int i, j, k;

   int n1 = m – l + 1;

   int n2 = r – m;

   int L[n1], R[n2];

   for (i = 0; i < n1; i++)

      L[i] = Arr[l + i];

   for (j = 0; j < n2; j++)

      R[j] = Arr[m + 1+ j];

   i = 0, j = 0, k = l;

   while (i < n1 && j < n2) {

      if (L[i] <= R[j]) {

         Arr[k] = L[i];

         i++;

      } else {

         Arr[k] = R[j];

         j++;

      }

      k++;

   }

   while (i < n1) {

      Arr[k] = L[i];

      i++;

      k++;

   }

   while (j < n2) {

      Arr[k] = R[j];

      j++;

      k++;

   }

}

void merge_sort(int Arr[], int N){

    for(int sub_size=1;sub_size<N;sub_size*=2)

    {

        for(int L=0; L<N; L+=(2*sub_size))

        {

            int Mid=min(L+sub_size-1,N-1);

            int R=min(L+2*sub_size-1,N-1);

            // function to merge  two sub-arrays of

            // size sub_size starting from L and Mid

            merge(Arr, L,Mid,R);

        }

    }

}

int main()

{

    int i;

    int N = 8;

    int Arr[N] = {3, 2, 1, 9, 5, 4, 10, 11};

    cout<<“Unsorted Array: “;

    for(i=0;i<N;i++)

        cout<<Arr[i]<<” “;

    cout<<endl;

    merge_sort(Arr, N);

    cout<<“Sorted Array: “;

    for(i=0;i<N;i++)

        cout<<Arr[i]<<” “;

    return 0;

}

Output:

Unsorted Array: 3 2 1 9 5 4 10 11

Sorted Array: 1 2 3 4 5 9 10 11

Output Explanation

Given: N = 8, Arr[] = {3, 2, 1, 9, 5, 4, 10, 11}

• When sub_size = 1

           Arr[] =  {2, 3, 1, 9, 4, 5, 10, 11}

• When sub_size = 2

           Arr[] =  {1, 2, 3, 9, 4, 5, 10, 11}

• When sub_size = 4

           Arr[] =  {1, 2, 3, 4, 5, 9, 10, 11}

Iterative Merge Sort Complexities

Time Complexity: Time complexity of the iterative merge sort is the same as the recursive merge sort.

• Worst-case time complexity: O(N*logN).
• Average-case time complexity: O(N*logN).
• Best-case time complexity: O(N*logN).

Space Complexity: In this algorithm, arrays L, R in the merge function take O(N) space. Therefore, the auxiliary space complexity is O(N).

Advantages of Iterative Merge Sort

• Worst-case, best-case, and average-case time complexity of merge sort are O(N*logN), making it very efficient.
• Iterative merge sort is slightly faster than recursive merge sort.

Disadvantages of Iterative Merge Sort

• Space complexity of iterative merge sort is O(N), whereas quicksort has O(1) space complexity.
• Recursive merge sort is easier to implement than iterative merge sort.
• Iterative merge sort is marginally slower than quicksort in practice.

To know more about the merge sort vs. quicksort, read:
Difference Between Merge Sort and Quicksort
Merge Sort vs. Quicksort: Algorithm Performance Analysis

FAQs on Iterative Merge Sort

Question 1: Is iterative merge sort stable?

Answer: Yes, iterative merge sort is an example of a stable sorting algorithm, as it does not change the relative order of elements of the same value in the input.

Question 2. Is iterative merge sort an in-place sorting algorithm?

Answer: No, iterative merge sort is not an in-place sorting algorithm. In in-place sorting algorithms, only a small/constant auxiliary space is used; in iterative merge sort, we use auxiliary lists to merge to sub-arrays.

Are You Ready to Nail Your Next Coding Interview?

If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

———-

Article contributed Abhinav Tiwari