The merge sort algorithm (implementation in Java)

1. Description

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)

2. Java implementation