## The merge sort algorithm (implementation in Java)

In computer science many algorithms are recursive by nature and they usually follow an approach called * divide-and-conquer* . In this particular case dividing-and-conquering a problems means to break it into smaller identical sub-problems, resolve the smaller sub-problems recursively (by dividing the smaller sub-problems into even smaller problems), and eventually combine all their results to determine the solution for the initial problem .

The **Merge Sort** algorithm is based on this technique :

1. The merge sort algorithm works on arrays (or lists). If the array has its size <= 1, then we consider the array already sorted and no change is done . This is considered to be the limit condition of this recursive approach . [Limit Condition] |

2. If size of the array (or list) > 1, then we divide the array into two equally-sized sub-arrays . [Divide] – O(1) |

3. At this point we recursively sort both of the two arrays . [Conquer] 2*T*(n/2) |

4. We merge the two sorted sub-arrays into one sorted array . [Merge] O(n) |

We will start by defining the MERGE function . This is function is responsible with the merging of two sorted arrays. The resulting array (in our case portion of the initial array composed by the two merged sub-arrays) will be also sorted :

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

Where:

L |
The initial unsorted array . |

llim |
The starting index of the left sub-array; |

mlim |
The stopping index for right sub-array, and the starting index for the right sub-array; |

rlim |
The stopping index for the right sub-array; |

LEFTL, RIGHTL |
Additional helper arrays . |

SENTINEL |
A value to simplify our code, there’s nothing “bigger” than the Sentinel . |

After we define the MERGE function, the actual MERGE-SORT function can be written as:

MERGESORT(L, start, stop) IF start < stop THEN middle := (start + stop) / 2 MERGESORT(L, start, middle) MERGESORT(L, middle + 1, stop) MERGE(L, start, middle, stop)