// java code for MergeSort
// adapted from Gittleman "Programs, Objects, Graphics"

public static void mergeSort(int[] x, int left, int right)
{  
    if (left<right)
      { 
        int middle=(left+right)/2;
        mergeSort(x, left, middle);
        mergeSort(x, middle+1, right);
        merge( x, left, middle, middle+1, right);
      }
}


public static void merge( int[] x, int left1, int right1, int left2, int right2)
{
  int oldPosition=left1;
  int size=right2-left1+1;
  int[] temp = new int[size];
  int i=0;                                  // i is an index for array temp
  while (left1<=right1 && left2<=right2)    //both subarrays are nonempty
     {
        if (x[left1]<= x[left2])  
           temp[i++] = x[left1++];
        else
           temp[i++] = x[left2++]; 
     }
  if (left1>right1)                  // first array is empty, copy rest of second
     for( int j=left2; j<=right2; j++)
         temp[i++] = x[left2++];
  else                              // second array is empty, copy rest of first
     for( int j=left1; j<=right1; j++)
         temp[i++] = x[left1++];
  System.arraycopy(temp, 0, x, oldPosition, size)  
}

//  arraycopy is method of the java.lang.System  class
//  parameters for arraycopy are:
//         source array
//         starting index in the source array at which to start copying
//         destination array
//         starting index in the destination array for the copied elements
//         number of elements to copy