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)