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

## 0 comments:

## Post a Comment