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 :

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:

2. Java implementation

Important note:

In order for the above code to work, ‘array’ should contain values smaller than Integer.MAX_VALUE (thus smaller than the chosen Sentinel) . The algorithm can of course be rewritten without the need of a sentinel value, this concept was introduced for the sake of code simplification .

2 thoughts on “The merge sort algorithm (implementation in Java)

  1. Pingback: Bottom-up Merge Sort (non-recursive) « andreINC.net

Leave a reply

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url=""> 

required

Are we human, or are we dancer *