## Bottom-up Merge Sort (non-recursive)

In the **last article** I’ve described a recursive version of the **Merge Sort Algorithm** . Of course every recursive algorithm can be written in an iterative manner . 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**) . Initially **step** is 1, but the value increases with every pass, as every adjacent sub-arrays are merged, thus **step** doubles .

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) .

FUNCTION MERGE(A, startL, stopL, startR, stopR) /* The leftArray is defined as containing all the elements from startL to stopL of A + a sentinel value */ LEFTL := [[A[llim]..A[mlim]) + SENTINEL] /* The right array is defined as containing all the elements from startR to stopR A + a sentinel value */ RIGHTL := [[A[mlim]..A[rlim]) + SENTINEL] i := 0 j := 0 FOR k:=llim TO rlim DO IF LEFTL[i] <= RIGHTL[j] THEN A[k] = LEFTL[i] i := i + 1 ELSE A[k] = RIGHTL[j] j := j + 1

And the actual function responsible with the actual merge can be written as follows:

FUNCTION MERGESORT(A, length) IF length < 2 THEN //RETURN - THE ARRAY IS ALREADY SORTED RETURN step := 1 WHILE step < length DO startL := 0 startR := step WHILE startR + step <= length DO MERGE(A, startL, startL + step, startR startR + step) startL := startR + step startR := startL + step IF startR < length THEN MERGE(A, startL, startL + step, startR, length) step := step * 2

Where **A **is the unsorted-but-soon-to-be-sorted array, **length** represents the size of **A**, **step **is the current size of the block, **startL **and **startR** represent the starting indexes of the sorted blocks that are going to be merged .

**2. Algorithm implementation in Java**