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:

## Java

Output:

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

## Python

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