Author
Abhinav Rawat
Product Manager @ Interview Kickstart | Ex-upGrad | BITS Pilani. Working with hiring managers from top companies like Meta, Apple, Google, Amazon etc to build structured interview process BootCamps across domains
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:
In Iterative merge sort, we implement merge sort in a bottom-up manner. This is how it works:
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.
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;
}
Unsorted Array: 3 2 1 9 5 4 10 11
Sorted Array: 1 2 3 4 5 9 10 11
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;
}
Unsorted Array: 3 2 1 9 5 4 10 11
Sorted Array: 1 2 3 4 5 9 10 11
Given: N = 8, Arr[] = {3, 2, 1, 9, 5, 4, 10, 11}
           Arr[] = {2, 3, 1, 9, 4, 5, 10, 11}
           Arr[] = {1, 2, 3, 9, 4, 5, 10, 11}
           Arr[] = {1, 2, 3, 4, 5, 9, 10, 11}
To know more about the merge sort vs. quicksort, read:
Difference Between Merge Sort and Quicksort
Merge Sort vs. Quicksort: Algorithm Performance Analysis
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.
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!
———-
Article contributed Abhinav Tiwari
Time Zone:
Get your enrollment process started by registering for a Pre-enrollment Webinar with one of our Founders.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
