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

Java

Download   Run Code

 
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 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
coder
Guest

Awesome code

Neeraj panchal
Guest

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!

santhosh
Guest

Really nice

MessiCR7
Guest

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?

scw
Guest

ArrayIndexOutOfBounds

[264, 84, 7, 57, -91, -422, 235, 390, 212, -190, 121, -447, -233, 74, -317, -105, -66, 27, 95, -149, 194, 151, -392]