In this post, we will see how to sort an array of integers using iterative merge sort algorithm.

Merge sort is an efficient sorting algorithm which falls under divide and conquer paradigm and produces a stable sort. It operates by dividing a large array into two smaller subarrays and then recursively sorting the subarrays.

In recursive approach, the problem is broken down into smaller, simple subproblems in top-down manner until the solution becomes trivial. We have already discussed merge sort algorithm in detail and covered recursive implementation here.

We can also implement merge sort iteratively in bottom-up manner. We start by sorting all subarrays of 1 element, then we merge results into subarrays of 2 elements, then we merge results into subarrays of 4 elements. Likewise, we perform successive merges until the array is completely sorted.

Below code proposes a non-recursive variant of the merge sort in C and Java, in which the array is sorted by a sequence of passes in bottom-up manner:

## C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <stdio.h> #include <time.h> #include <stdlib.h> #define N 15 // Utility function to find minimum of two numbers int min(int x, int y) { return (x < y) ? x : y; } // Merge two sorted subarrays A[from .. mid] and A[mid + 1 .. to] void merge(int A[], int temp[], int from, int mid, int to) { int k = from, i = from, j = mid + 1; // loop till there are elements in the left and right runs while (i <= mid && j <= to) { if (A[i] < A[j]) temp[k++] = A[i++]; else temp[k++] = A[j++]; } // Copy remaining elements while (i < N && i <= mid) temp[k++] = A[i++]; // Don't need to copy second half // copy back to the original array to reflect sorted order for (int i = from; i <= to; i++) A[i] = temp[i]; } // Iteratively sort array A[low..high] using temporary array void mergesort(int A[], int temp[], int low, int high) { // divide the array into blocks of size m // m = [1, 2, 4, 8, 16...] for (int m = 1; m <= high - low; m = 2*m) { // for m = 1, i = 0, 2, 4, 6, 8 // for m = 2, i = 0, 4, 8 // for m = 4, i = 0, 8 // ... for (int i = low; i < high; i += 2*m) { int from = i; int mid = i + m - 1; int to = min(i + 2*m - 1, high); // cout << from << " " << to << endl; merge(A, temp, from, mid, to); } } } // Utility function to print an given array int printArray(int A[]) { for (int i = 0; i < N; i++) { printf("%d ", A[i]); } printf("\n"); } // Implement Iterative Merge Sort int main() { int A[N], temp[N]; srand(time(NULL)); // generate random input of integers for (int i = 0; i < N; i++) temp[i] = A[i] = (rand() % 50); printf("Original Array : "); printArray(A); // sort array A[0..N-1] using temporary array temp mergesort(A, temp, 0, N - 1); printf("Modified Array : "); printArray(A); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
import java.util.Arrays; class MergeSort { // Merge two sorted sub-arrays A[from .. mid] and A[mid + 1 .. to] public static void merge(int[] A, int[] temp, int from, int mid, int to) { int k = from, i = from, j = mid + 1; // loop till there are elements in the left and right runs while (i <= mid && j <= to) { if (A[i] < A[j]) { temp[k++] = A[i++]; } else { temp[k++] = A[j++]; } } // Copy remaining elements while (i <= mid) { temp[k++] = A[i++]; } // Don't need to copy second half // copy back to the original array to reflect sorted order for (i = from; i <= to; i++) { A[i] = temp[i]; } } // Iteratively sort array A[low..high] using temporary array public static void mergesort(int[] A) { int low = 0; int high = A.length - 1; // sort array A[] using temporary array temp int[] temp = Arrays.copyOf(A, A.length); // divide the array into blocks of size m // m = [1, 2, 4, 8, 16...] for (int m = 1; m <= high - low; m = 2*m) { // for m = 1, i = 0, 2, 4, 6, 8... // for m = 2, i = 0, 4, 8, 12... // for m = 4, i = 0, 8, 16... // ... for (int i = low; i < high; i += 2*m) { int from = i; int mid = i + m - 1; int to = Integer.min(i + 2 * m - 1, high); merge(A, temp, from, mid, to); } } } // Iterative Implementation of Mergesort algorithm public static void main(String[] args) { int[] A = { 5, 7, -9, 3, -4, 2, 8 }; System.out.println("Original Array : " + Arrays.toString(A)); mergesort(A); System.out.println("Modified Array : " + Arrays.toString(A)); } } |

The worst case time complexity of iterative merge sort remains same as recursive implementation i.e. O(nlog(n)) but saves auxiliary space required by the call stack.

**Related Post:** External Mergesort

**References:** http://csg.sph.umich.edu/abecasis/class/2006/615.09.pdf

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Awesome code

I was Google around for content Sorting Algorithms in Objective – C this morning, when I came across your excellent page.

Great stuff!!

I just wanted to say that your page helped me a ton. I would have never found any deep insight article Sorting Algorithms in Objective – C. I specially like you how you add deep information on blog,

It helps to setup Sorting Algorithms in Objective

It’s funny: I recently published top online resources to learn Sorting Algorithms in Objective – C

.

Here it is in case you’d like to check it out: https://hackr.io/blog/merge-sort-in-c

Also, my tutorial might make a nice addition for learning sorting.

Either way, thanks. And have a great day!

Really nice

What’s the reason for checking if the array is properly sorted or not? If the algorithm is correct, there’s no need to check it, I assume?

It was added just to prove correctness of the algorithm. We have removed it from the code now.

ArrayIndexOutOfBounds

[264, 84, 7, 57, -91, -422, 235, 390, 212, -190, 121, -447, -233, 74, -317, -105, -66, 27, 95, -149, 194, 151, -392]Thanks a lot for bringing this issue to our notice. We have updated the code.