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:


Download   Run Code


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


1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

Awesome code

Neeraj panchal

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:

Also, my tutorial might make a nice addition for learning sorting.

Either way, thanks. And have a great day!


Really nice


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?



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