// taken with modifications from
// R.Lafore, `Data structures and algorithms in Java'.

class Merge{

//----------------------------------------------------------- 
   public static void mergeSort(int[] arr)           // called by main() 
      {                                              // provides workspace 
      int[] workSpace = new int[arr.length]; 
      recMergeSort(arr, workSpace, 0, arr.length-1); 
      } 
//----------------------------------------------------------- 
   private static void recMergeSort(int[] arr, int[] workSpace, int lowerBound, 
                                                 int upperBound) 
      { 
      if(lowerBound == upperBound)                              // if range is 1, 
         return;                                                // no use sorting 
      else 
         {                                                      
         int mid = (lowerBound+upperBound) / 2;                 // find midpoint 
         recMergeSort(arr, workSpace, lowerBound, mid);         // sort low half
         recMergeSort(arr, workSpace, mid+1, upperBound);       // sort high half
         merge(arr, workSpace, lowerBound, mid+1, upperBound);  // merge them
// System.out.println("Merging range: " + lowerBound + " - " + upperBound);
         }  // end else 
      }  // end recMergeSort() 
//----------------------------------------------------------- 
   private static void merge(int[] arr, int[] workSpace, int lowPtr, 
                      int highPtr, int upperBound) 
      { 
      int j = 0;                             // workspace index 
      int lowerBound = lowPtr; 
      int mid = highPtr-1; 
      int n = upperBound-lowerBound+1;       // # of items 
 
      while(lowPtr <= mid && highPtr <= upperBound) 
         if( arr[lowPtr] < arr[highPtr] ) 
            workSpace[j++] = arr[lowPtr++]; 
         else 
            workSpace[j++] = arr[highPtr++]; 
 
      while(lowPtr <= mid) 
         workSpace[j++] = arr[lowPtr++]; 
 
      while(highPtr <= upperBound) 
         workSpace[j++] = arr[highPtr++]; 
 
      for(j=0; j<n; j++) 
         arr[lowerBound+j] = workSpace[j]; 
      }  // end merge() 
//------------------------------------------------------------- 
   
    public static void main(String[] args)
       {
       // create an int[] array and call
       // mergeSort(array);
        
    }// end main()
//-------------------------------------------------------------

}  // end class Merge