Sorting Arrays in Java with MergeSort

Introduction

• This series is not going to be in any particular order, so feel free to read whatever blog post you want. Anytime I find write something about Computer Science I will put it here.

Source code

• The source code can be found HERE

Flow chart

• I made a flow chart to better show the recursive nature of MergeSort and it can be found HERE. The flow chart is sorting the array of [3,2,1]

MergeSort

• So this algorithm is based on a simple operation called merging. When 2 ordered arrays are combined to make one larger ordered array. This kind of operation lends itself to a simple recursive sort called MergeSort. To sort an array with MergeSort , divide the array into two halves(recursively), sort and merge the results

• MergeSort's worst case run time is NlogN. It's prime disadvantage is that it uses extra space.

Comparable interface

• Before we go any farther we first need to talk about the Comparable interface, because when we implement the code you will see a lot of, Comparable[] a. This defines an array that is full of comparables.
• Ok, but why do we use it? Well, in our merge() method we need a way to compare two items. Of course you could just create different code for Strings, Integers and so on. However, If we use the Comparable interface we do not have to. Every built in type in Java has what is called, a natural ordering, The full list of all the types that have this ordering can be found HERE. They have this ordering because they implement the Comparable interface. as you will see in our code, we use the compareTo() method to exploit this natural ordering allowing us to compare Strings, Integers and even Dates. So in a way the Comparable[] array allows to create a generic array for sorting.

Recursion

• If you are already familiar with stacks and stack frames feel free to skip this part
• So what exactly is recursion? It is a technique by which a method makes more calls to itself during execution. This may sound confusing so look at the code below:

public void recursiveMethod(){
  recursiveMethod();
}

• But what actually happens when recursiveMethod() method is called? When the JVM invokes a Java method, the JVM creates a new stack frame and adds it to the top of the Stack. This new frame then becomes the current frame. As the method executes it, it uses this frame to store parameters, local variables and all the other necessary data needed by the method. Confused? Good that means we are learning!!!!

Stack: When you read the term stack, think of a collection of objects that are inserted and removed accordingly to the last-in, first out principle. You can insert objects into a stack at anytime but only the most recently added objects on the stack can be accessed or removed. A good visualization of the stack can be found HERE.

Stack Frame: when talking about the stack frame things can get a little complicated and if you would like a more detailed explanation I would recommend the blog post, HERE. Essentially each time a method is called the JVM creates a box of all the necessary information that the method needs and adds that box to the stack. When the method returns its box is removed (popped) from the stack

Why this method does not return anything

• As you will soon see, this implementation of MergeSort does not return anything and yet the array still gets sorted. At first this might seem a little bit like magic but this is software,THERE IS NO MAGIC IN SOFTWARE!!! ONLY HARDWORD AND DEDICATION. This is done because while Java is technically pass by value, all the a and aux variables are still referencing the same array object in memory. So all operations are done on the same a and aux objects

Implementing MergeSort

• To implement MergeSort we will create 3 methods:

1) public sort : this method's job is to take in the desired array to be sorted, create a auxiliary array later used for merging and to call the private sort method .

2) private sort : this private sort method's job is to divide up the array so it can be sorted is a recursive fashion.

3) private merge : this method does all the heavy lifting of comparing each item and merging it back into its proper place of the starting array.

public sort

• This method really has two main jobs:

1) : create the auxiliary method
2) : call the private sort method

• The implementation would look like this:

  public static void sort(Comparable [] a){
       Comparable[] aux = new Comparable[a.length];
       sort(a,aux,0,a.length -1);
   }

• I would like to point out that there is no really need for the method to be static. It is simply for ease of use. You can just as easily make all these methods non static.

private sort

• This is the method where we make the recursive calls. It is the recursive calls that allow us to "split up" the array for merging. Now I put "split up" in quotations because this version of merge sort does not do any actual splitting. As you can see from the flow chart HERE we are only sorting sections of the array and then moving to the next section. I am trying to stress this because many other versions of MergeSort actually split the starting array into smaller and smaller arrays before merging them back together.
• The implementation is below:

public static void sort(Comparable[] a,Comparable[] aux,int lo, int hi){
   if(hi<=lo) return;
   int mid = lo +(hi-lo) /2;
   sort(a,aux,lo,mid);
   sort(a,aux,mid+1,hi);
   merge(a,aux,lo,mid,hi);

}

• First notice our base case, f(hi<=lo) return;, every recursive method needs one. This is to prevent out method from continuously calling itself. Next look at, int mid = lo +(hi-lo) /2;. This is very important because it is what is splitting up the array for the merging. Notice the two calls to sort(), sort(a,aux,lo,mid); and sort(a,aux,mid+1,hi); notice where mid is. it first acts as the hi parameter and then the lo parameter.

• Now I find recursion to be very complicated to explain in text format, so I created a flow chart which can be found HERE, to better explain its recursive nature.

private merge

• This is the method where all the work is done. It is responsible for comparing items and merging the sorted variables back into our a array. This method can be broken down into two main sections:

1) copy to aux : this is where we loop over the a array and copy it to our aux array. We do this to make sorting easier.

for(int k =lo ; k <=hi; k++){
  aux[a] = a[k]
}

• obviously the amount of times this loops over a is dependant on the lo and hi parameters. See flow chart to get specific understandings HERE.

2) merge back to a : this is the part where we actually compare, sort and then merge the variables back into a. The implementation looks like this;

int i = lo, j = mid+1
for(int k = lo, k<=hi; k++){
   if(i>mid)                   a[k] = aux[j++];
   else if(j > hi)             a[k] = aux[i++];
   else if(less(aux[j],aux[i)) a[k]= aux[j++];
   else                        a[k] = aux[i++];

}

• First lets talk about the utility method less(aux[j],aux[i). That method looks like this:

public static boolean less(Comparable v, Comparable w){
   return v.compareTo(w) < 0;

• As mentioned earlier the compareTo() method is allows us to compare two parameters and determine which one is greater than the other.

• The variables int i = lo, j = mid+1 are straight forward, the only reason we us mid+1 for j is because there are times when lo and mid are the same number.

• The for loop is the exact same as the loop from the copy to aux stage and the conditionals are what do the actual sorting.

Full implementation

 public static void sort(Comparable [] a){
       Comparable[] aux = new Comparable[a.length];
       sort(a,aux,0,a.length -1);
   }

   private static void sort(Comparable[] a, Comparable[] aux, int lo,int hi){
       if(hi<=lo) return;
       int mid = lo + (hi - lo) / 2;
       sort(a,aux,lo,mid);
       sort(a,aux,mid+1,hi);
       merge(a,aux,lo,mid,hi);
   }
   private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi){

       //copy to aux
       for(int k = lo; k <= hi; k ++){
           aux[k] = a[k];
       }

       //merge to a
       int i = lo, j = mid +1;
       for(int k = lo; k <= hi; k ++){
           if(i > mid)                  a[k] = aux[j++];
           else if(j > hi)              a[k] = aux[i++];
           else if(less(aux[j],aux[i])) a[k] = aux[j++];
           else                         a[k] = aux[i++];
       }

   }

    /**********************************************
     * HELPER SORTING FUNCTIONS
     **********************************************/
     private static boolean less(Comparable v, Comparable w){
         return v.compareTo(w) < 0;
     }

• As you can see the full implementation is actually very clean and easy to implement.

Conclusion

• Thank you for taking the time out of your day to read this blog post of mine. If you have any questions or concerns please comment below or reach out to me on Twitter.