Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Iterative Merge Sort
Hosted By
Ryan Valles
Founder, Interview Kickstart
strategy
Our tried & tested strategy for cracking interviews
prepare list
How FAANG hiring process works
hiring process
The 4 areas you must prepare for
hiring managers
How you can accelerate your learnings
The fast well prepared banner

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



Last updated on: 
October 27, 2023
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

Attend our Free Webinar on How to Nail Your Next Technical Interview

Square

Iterative Merge Sort

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Our tried & tested strategy for cracking interviews
blue tick
How FAANG hiring process works
blue tick
The 4 areas you must prepare for
blue tick
How you can accelerate your learnings
Register for Webinar
entroll-image