/**
Merge Sort, written to work with Comparable objects.
@author Melvin Fitting
@version March, 2003
*/

public class MergeSort
{
   public static void sort(Comparable[] list)
   {
      sort(list, 0, list.length);
   }

   private static void merge(Comparable[] list, int a, int b, int c)
   {
      Comparable[] temp = new Comparable[c-a];
      int first = a;
      int second = b;
      int tempPointer = 0;
      while(first < b && second < c)
      {
         if(list[first].compareTo(list[second]) < 0)
            temp[tempPointer] = list[first++];
         else
            temp[tempPointer] = list[second++];
         tempPointer++;
      }
      while(first < b)
      {
         temp[tempPointer] = list[first];
         first++;
         tempPointer++;
      }
      while(second < c)
      {
         temp[tempPointer] = list[second];
         second++;
         tempPointer++;
      }
      for(int n = 0; n < temp.length; n++)
         list[n+a] = temp[n];
   }

   private static void sort(Comparable[] list, int a, int b)
   {
      if (b-a > 1)
      {
         int c = (a+b)/2;
         sort(list, a, c);
         sort(list, c, b);
         merge(list, a, c, b);
      }
   }
}