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

1. Algorithm Description

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