This post will sort an integer array using the iterative merge sort algorithm.

Merge sort is an efficient sorting algorithm that falls under the 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 a recursive approach, the problem is broken down into smaller, simple subproblems in a top-down manner until the solution becomes trivial. We have already discussed the merge sort algorithm in detail and covered recursive implementation here.

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

Practice this algorithm

The following code proposes a non-recursive variant of the merge sort in C, Java, and Python, in which a sequence of passes sorts the array in a bottom-up manner:

C


Download  Run Code

Java


Download  Run Code

Output:

Original array: [5, 7, -9, 3, -4, 2, 8]
Modified array: [-9, -4, 2, 3, 5, 7, 8]

Python


Download  Run Code

Output:

Original array: [5, 7, -9, 3, -4, 2, 8]
Modified array: [-9, -4, 2, 3, 5, 7, 8]

The worst-case time complexity of iterative merge sort remains the same as the recursive implementation, i.e., O(n.log(n)) for an input containing n items. However, it saves the auxiliary space required by the call stack.

 
Also See:

External Merge Sort Algorithm

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