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

An alternative implementation is the **bottom-up** version of the same algorithm (we don’t use recursion for this implementation).

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

- We consider an array with size
`<= 1`

sorted; - The array that needs to be sorted is
`A = { 5, 2, 1, 12, 2, 10, 4, 13, 5}`

. At this point`step=1`

- 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}`

; `step *= 2 -> 1 * 2 = 2`

: At this point we have a collection of sorted sub-arrays (because their`size=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;`step *= 2 -> 2 * 2 = 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}`

;`step *= 2 -> 2 * 4 = 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}`

- 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}`

.

# Pseudo-Code

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`

is 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
```

The actual `MERGESORT()`

is:

```
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

# Java Implementation

```
public class NonRecursiveMergeSort {
// Print Array
public static void printArray(int[] array){
for(int i : array) {
System.out.printf("%d ", i);
}
System.out.printf("n");
}
// Bottom-up merge sort
public static void mergeSort(int[] array) {
if(array.length < 2) {
// We consider the array already sorted, no change is done
return;
}
// The size of the sub-arrays . Constantly changing .
int step = 1;
// startL - start index for left sub-array
// startR - start index for the right sub-array
int startL, startR;
while(step < array.length) {
startL = 0;
startR = step;
while(startR + step <= array.length) {
mergeArrays(array, startL, startL + step, startR, startR + step);
// System.out.printf("startL=%d, stopL=%d, startR=%d, stopR=%dn",
// startL, startL + step, startR, startR + step);
startL = startR + step;
startR = startL + step;
}
// System.out.printf("- - - with step = %dn", step);
if(startR < array.length) {
mergeArrays(array, startL, startL + step, startR, array.length);
// System.out.printf("\* startL=%d, stopL=%d, startR=%d, stopR=%dn",
// startL, startL + step, startR, array.length);
}
step *= 2;
}
}
// Merge to already sorted blocks
public static void mergeArrays(int[] array, int startL, int stopL,
int startR, int stopR) {
// Additional arrays needed for merging
int[] right = new int[stopR - startR + 1];
int[] left = new int[stopL - startL + 1];
// Copy the elements to the additional arrays
for(int i = 0, k = startR; i < (right.length - 1); ++i, ++k) {
right[i] = array[k];
}
for(int i = 0, k = startL; i < (left.length - 1); ++i, ++k) {
left[i] = array[k];
}
// Adding sentinel values
right[right.length-1] = Integer.MAX_VALUE;
left[left.length-1] = Integer.MAX_VALUE;
// Merging the two sorted arrays into the initial one
for(int k = startL, m = 0, n = 0; k < stopR; ++k) {
if(left[m] <= right[n]) {
array[k] = left[m];
m++;
}
else {
array[ks] = right[n];
n++;
}
}
}
public static void main(String[] args) {
// Beacuse of the chosen Sentinel the array
// should contain values smaller than Integer.MAX\_VALUE .
int[] array = new int[] { 5, 2, 1, 12, 2, 10, 4, 13, 5};
mergeSort(array);
printArray(array);
}
}
```

## Comments