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, in which the array is sorted by a sequence of passes in bottom-up manner:

 

Download   Run Code

Output:

6 8 10 11 23 25 26 35 38 43

 
The worst case time complexity of iterative merge sort remains same as recursive implementation i.e. O(nlog(n)). But auxiliary space required by the merge sort is improved from linear to O(1).

 
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

Notify of
avatar
wpDiscuz