Open In App

Iterative Merge Sort

Last Updated : 20 Feb, 2025
Suggest changes
Share
Like Article
Like
Report

Given an array of size n, the task is to sort the given array using iterative merge sort.

Examples:

Input: arr[] = [4, 1, 3, 9, 7]
Output: [1, 3, 4, 7, 9]
Explanation: The output array is sorted.

Input: arr[] = [1, 3 , 2]
Output: [1, 2, 3]
Explanation: The output array is sorted.

You can refer to Merge Sort – Data Structure and Algorithms Tutorials for typical recursive solution.

Approach: 

The idea is to implement an iterative merge sort that avoids recursion by taking a bottom-up approach, starting with individual elements and progressively merging sorted subarrays of increasing sizes (1, 2, 4, 8...), where at each level we pair adjacent subarrays and merge them until the entire array is sorted.

Detailed Explanation:

  1. In traditional recursive merge sort, we use a top-down approach where we keep dividing the array until we reach individual elements. However, this requires maintaining a function call stack and involves overhead from function calls.
  2. The iterative version eliminates this overhead by working bottom-up. We start by considering each element as a sorted subarray of size 1. Then in each pass, we merge adjacent pairs of these sorted subarrays to create larger sorted subarrays.
  3. The outer loop controls the size of subarrays being merged (currSize), which doubles in each iteration (1, 2, 4, 8...). For each size, we iterate through the array to find pairs of adjacent subarrays to merge.
  4. A key insight is handling array sizes that aren't powers of 2. For example, with 7 elements, when merging size-2 subarrays, we might have pairs like (2,2,2,1). The algorithm handles this by using the min function to correctly calculate the endpoints of subarrays.
C++ 
// C++ program to perform // iterative merge sort. #include <iostream> #include <vector> using namespace std; // Helper function to merge two sorted portions of the vector void merge(vector<int>& arr, int left, int mid, int right) {    int n1 = mid - left + 1;  int n2 = right - mid;    // Create temporary vectors   // for left and right subarrays  vector<int> arr1(n1), arr2(n2);    // Copy data to temporary vectors  for (int i = 0; i < n1; i++)  arr1[i] = arr[left + i];  for (int j = 0; j < n2; j++)  arr2[j] = arr[mid + 1 + j];    int i = 0;   int j = 0;   int k = left;     // Merge the temp vectors back into arr  while (i < n1 && j < n2) {  if (arr1[i] <= arr2[j]) {  arr[k] = arr1[i];  i++;  } else {  arr[k] = arr2[j];  j++;  }  k++;  }    // Copy remaining elements of arr1[] if any  while (i < n1) {  arr[k] = arr1[i];  i++;  k++;  }    // Copy remaining elements of arr2[] if any  while (j < n2) {  arr[k] = arr2[j];  j++;  k++;  } } // Main sorting function void mergeSort(vector<int>& arr) {  int n = arr.size();    // Iterate through subarrays of increasing size  for (int currSize = 1; currSize <= n-1;   currSize = 2*currSize) {    // Pick starting points of different  // subarrays of current size  for (int leftStart = 0; leftStart < n-1;   leftStart += 2*currSize) {    // Find endpoints of the subarrays to be merged  int mid = min(leftStart + currSize - 1, n-1);  int rightEnd = min(leftStart + 2*currSize - 1, n-1);    // Merge the subarrays arr[leftStart...mid]  // and arr[mid+1...rightEnd]  merge(arr, leftStart, mid, rightEnd);  }  } } int main() {  vector<int> arr = {4, 1, 3, 9, 7};    mergeSort(arr);  for (auto val: arr)   cout << val << " "; }
Java 
// Java program to perform // iterative merge sort. import java.util.*; class GfG {    // Helper function to merge two sorted portions of the array  static void merge(int[] arr, int left, int mid, int right) {    int n1 = mid - left + 1;  int n2 = right - mid;    // Create temporary arrays   // for left and right subarrays  int[] arr1 = new int[n1], arr2 = new int[n2];    // Copy data to temporary arrays  for (int i = 0; i < n1; i++)  arr1[i] = arr[left + i];  for (int j = 0; j < n2; j++)  arr2[j] = arr[mid + 1 + j];    int i = 0;   int j = 0;   int k = left;     // Merge the temp arrays back into arr  while (i < n1 && j < n2) {  if (arr1[i] <= arr2[j]) {  arr[k] = arr1[i];  i++;  } else {  arr[k] = arr2[j];  j++;  }  k++;  }    // Copy remaining elements of arr1[] if any  while (i < n1) {  arr[k] = arr1[i];  i++;  k++;  }    // Copy remaining elements of arr2[] if any  while (j < n2) {  arr[k] = arr2[j];  j++;  k++;  }  }  // Main sorting function  static void mergeSort(int[] arr) {  int n = arr.length;    // Iterate through subarrays of increasing size  for (int currSize = 1; currSize <= n - 1;   currSize = 2 * currSize) {    // Pick starting points of different  // subarrays of current size  for (int leftStart = 0; leftStart < n - 1;   leftStart += 2 * currSize) {    // Find endpoints of the subarrays to be merged  int mid = Math.min(leftStart + currSize - 1, n - 1);  int rightEnd = Math.min(leftStart + 2 * currSize - 1, n - 1);    // Merge the subarrays arr[leftStart...mid]  // and arr[mid+1...rightEnd]  merge(arr, leftStart, mid, rightEnd);  }  }  }  public static void main(String[] args) {  int[] arr = {4, 1, 3, 9, 7};    mergeSort(arr);    for (int val : arr) {  System.out.print(val + " ");  }  } }
Python 
# Python program to perform # iterative merge sort. # Helper function to merge two sorted portions of the list def merge(arr, left, mid, right): n1 = mid - left + 1 n2 = right - mid # Create temporary lists  # for left and right subarrays arr1 = arr[left:left + n1] arr2 = arr[mid + 1:mid + 1 + n2] i = 0 j = 0 k = left # Merge the temp lists back into arr while i < n1 and j < n2: if arr1[i] <= arr2[j]: arr[k] = arr1[i] i += 1 else: arr[k] = arr2[j] j += 1 k += 1 # Copy remaining elements of arr1[] if any while i < n1: arr[k] = arr1[i] i += 1 k += 1 # Copy remaining elements of arr2[] if any while j < n2: arr[k] = arr2[j] j += 1 k += 1 # Main sorting function def mergeSort(arr): n = len(arr) # Iterate through subarrays of increasing size currSize = 1 while currSize <= n - 1: # Pick starting points of different # subarrays of current size leftStart = 0 while leftStart < n - 1: # Find endpoints of the subarrays to be merged mid = min(leftStart + currSize - 1, n - 1) rightEnd = min(leftStart + 2 * currSize - 1, n - 1) # Merge the subarrays arr[leftStart...mid] # and arr[mid+1...rightEnd] merge(arr, leftStart, mid, rightEnd) leftStart += 2 * currSize currSize = 2 * currSize if __name__ == "__main__": arr = [4, 1, 3, 9, 7] mergeSort(arr) print(" ".join(map(str, arr)))
C# 
// C# program to perform // iterative merge sort. using System; class GfG {  // Helper function to merge two sorted portions of the array  static void merge(int[] arr, int left, int mid, int right) {    int n1 = mid - left + 1;  int n2 = right - mid;    // Create temporary arrays   // for left and right subarrays  int[] arr1 = new int[n1], arr2 = new int[n2];    int i, j;    // Copy data to temporary arrays  for (i = 0; i < n1; i++)  arr1[i] = arr[left + i];  for (j = 0; j < n2; j++)  arr2[j] = arr[mid + 1 + j];    i = 0;   j = 0;   int k = left;     // Merge the temp arrays back into arr  while (i < n1 && j < n2) {  if (arr1[i] <= arr2[j]) {  arr[k] = arr1[i];  i++;  } else {  arr[k] = arr2[j];  j++;  }  k++;  }    // Copy remaining elements of arr1[] if any  while (i < n1) {  arr[k] = arr1[i];  i++;  k++;  }    // Copy remaining elements of arr2[] if any  while (j < n2) {  arr[k] = arr2[j];  j++;  k++;  }  }  // Main sorting function  static void mergeSort(int[] arr) {  int n = arr.Length;    // Iterate through subarrays of increasing size  for (int currSize = 1; currSize <= n - 1;   currSize = 2 * currSize) {    // Pick starting points of different  // subarrays of current size  for (int leftStart = 0; leftStart < n - 1;   leftStart += 2 * currSize) {    // Find endpoints of the subarrays to be merged  int mid = Math.Min(leftStart + currSize - 1, n - 1);  int rightEnd = Math.Min(leftStart + 2 * currSize - 1, n - 1);    // Merge the subarrays arr[leftStart...mid]  // and arr[mid+1...rightEnd]  merge(arr, leftStart, mid, rightEnd);  }  }  }  static void Main() {  int[] arr = {4, 1, 3, 9, 7};    mergeSort(arr);    Console.WriteLine(string.Join(" ", arr));  } }
JavaScript 
// JavaScript program to perform // iterative merge sort. // Helper function to merge two sorted portions of the array function merge(arr, left, mid, right) {    let arr1 = arr.slice(left, mid + 1);  let arr2 = arr.slice(mid + 1, right + 1);    let i = 0, j = 0, k = left;    while (i < arr1.length && j < arr2.length) {  arr[k++] = arr1[i] <= arr2[j] ? arr1[i++] : arr2[j++];  }    while (i < arr1.length) arr[k++] = arr1[i++];  while (j < arr2.length) arr[k++] = arr2[j++]; } // Main sorting function function mergeSort(arr) {  let n = arr.length;    for (let currSize = 1; currSize <= n - 1; currSize *= 2) {  for (let leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {  let mid = Math.min(leftStart + currSize - 1, n - 1);  let rightEnd = Math.min(leftStart + 2 * currSize - 1, n - 1);  merge(arr, leftStart, mid, rightEnd);  }  } } // Driver Code let arr = [4, 1, 3, 9, 7]; mergeSort(arr); console.log(arr.join(" "));

Output
1 3 4 7 9

Time complexity: O(n * log n) 
Space Complexity: O(n)


Next Article
In-Place Merge Sort

K

kartik

Similar Reads

Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy  Cookies are not collected in the GeeksforGeeks mobile applications.
Lightbox