Iterative Merge Sort Algorithm (Bottom-up Merge Sort)

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

Download   Run Code

Output:

2 3 5 6 8 23 34 39 43 49

Java

Download   Run Code

Output:

[2, 3, 4, 5, 7, 8, 9]

 
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 ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
coder
Guest
coder

The algorithm is failing for the array A = {5, 3, 4, 2, 1}

santhosh
Guest
santhosh

Really nice

MessiCR7
Guest
MessiCR7

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?