Bottom-up Merge Sort

Recursive algorithm
In the earlier article I’ve described a recursive version of the Merge Sort Algorithm OR Top Down Merge sort. Of course every recursive algorithm can be written in an iterative manner .

Non recursive algorithm
So today I am going to present the bottom-up version of the same algorithm, written in a non-recursive fashion .
The main idea of the bottom-up merge sort is to sort the array in a sequence of passes . During each pass the array is divided into smaller sub-arrays of a pseudo-fixed size (step or sz) . Initially step is 1, but the value increases with every pass, as every adjacent sub-arrays are merged, thus step doubles .
Top Down vs Bottom up sort

Top down	Bottom up
Recursive	Non recursive
It is top down, as we break the array into 2 halves, and these halves into further sub halves and so on, sort them and merge again	Here we dont break into halves, rather we have a step, which determines the size of the array to be broken. Initially it is one, we sort the array of size equal to step and go further
Has more number of iterations	Has lesser number of iterations
Professor Kevin wayne (of Princeton) replied that in many cases recursion is faster than iteration because of caching improved performances.	Algorithm wise it is as fast as top down, but may be slower as current implementation provide faster support for recursion

Example

0. We consider an array with size <= 1 sorted .

1. The array that needs to be sorted is A = { 5, 2, 1, 12, 2, 10, 4, 13, 5} . At this point step = 1 .

2. At the first iteration array A is divided into blocks of size step = 1 . The resulting blocks (sub-arrays) are {5}, {2}, {1}, {12}, {2}, {10}, {4}, {13}, {5} .

3. step *= 2, thus step is now 2 . At this point we have a collection of sorted sub-arrays (because their size is = 1) . We will group the sub-arrays one-by-one and we will start merging them . After the merge, the resulting sub-arrays are: {2, 5}, {1,12}, {2,10}, {4, 13} and {5} . {5} remains unpaired as the array size is an odd number . We will take care of this block later .

4. step *= 2, thus step is now 4 . Now we have a collection of 4 blocks of size two and one block of size one . We will start to merge again the adjacent blocks, so the sub-arrays collection becomes: {1, 2, 5, 12}, {2, 4, 10, 13} and {5} .

5. step *= 2, thus step is now 8 . Now we have a collection of 2 blocks with size 4 and one block with size 1 . We will merge the adjacent blocks so the sub-arrays collection becomes {1, 2, 2, 4, 5, 10, 12, 13} and {5} .

6. We now have two blocks one of size 8 and one of size 1 . We will merge those blocks and obtain the resulting sorted array: {1, 2, 2, 4, 5, 5, 10, 12, 13} .

The pseudo code for the algorithm can be written as follows . We will start by writing the merge function . This is responsible with the merging of two already sorted blocks (sub-arrays) from a given array . The input parameters for this function are : the array itself, and the interval headers (stop, start) for the two already sorted blocks . The sentinel is a concept that simplifies the code . In our case we consider SENTINEL infinity (no value from the array is bigger or equal to the Sentinel) .