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

1. We consider an array with size `<= 1` sorted;
2. The array that needs to be sorted is `A = { 5, 2, 1, 12, 2, 10, 4, 13, 5}`. At this point `step=1`
3. 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}`;
4. `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;
5. `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}`;
6. `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}`
7. 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];
}

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

Updated: