public class MergeSort{
	  public static void main(String [] args){
	    int[] grades = {89, 94, 69, 80, 97, 85, 73, 91, 77, 93};
	    System.out.println("Unsorted values");
	    output(grades);
	    MergeSort(grades);
	    System.out.println("Sorted values");
	    output(grades);
	  }
	 
	  public static void MergeSort(int[] originalList){
	    int[] leftList, rightList;
	    int aptr, bptr, cptr;
	    aptr = 0;
	    bptr = 0;
	    cptr = 0;
	    int left = originalList.length / 2;
	    int right = originalList.length - left;
	    leftList = new int[left];
	    rightList = new int[right];
	 
	    if (originalList.length > 1){
	      // form liftList
	      for(int i = 0; i < left; ++i){
	        leftList[i] = originalList[i];
	      }
	      // form rightList
	      for(int i = 0; i < right; ++i){
	        rightList[i] = originalList[i + left];
	      }
	    
	      MergeSort(leftList);
	      MergeSort(rightList);
	    }
	    else{ // you need a base case for recursive function
	      return; // base case is: originalListsize < 2
	    }
	 
	    // merge leftList and rightList into originalList of each recursion
	    while((aptr < left) && (bptr < right)){
	      if (leftList[aptr] < rightList[bptr]){
	        originalList[cptr++] = leftList[aptr++];
	      }
	      else{
	        originalList[cptr++] = rightList[bptr++];
	      }
	    }
	 
	    while(aptr < left){ // right is already empty but left is not
	      originalList[cptr++] = leftList[aptr++];
	    }
	 
	    while(bptr < right){ // left is already empty but right is not
	      originalList[cptr++] = rightList[bptr++];
	    } 
	  }
	 
	  public static void output(int[] data){
	    for(int i = 0; i < data.length; ++i){
	      System.out.print(data[i] + " ");
	    }
	    System.out.println();
	  }
	}