class Merge1{
 
 
  public static void main (String [] args) {
 
  int [] arr = { 0,1,0,100,89,2,76,31,8,52,15,21,32,44,55,66,1,10,4};

  printarr(arr);
  mergesort(arr,0, arr.length-1);
  
  printarr(arr);


}
 static void mergesort(int [] arr, int first, int last){
  int d=(last+first)/2;
  if ( first<last ) {
     if (d==first)++d;
         mergesort(arr,first, d-1);
         mergesort(arr,d, last);
         merge(arr,first,d, last+1);

   }
  }


  static void printarr(int [] r){
           for (int i=0;i<r.length;++i)
                 System.out.print(r[i]+" "); 
           System.out.println();
      } 

static  void merge(int [] arr, int first, int d, int n) {
        int [] r = new int [n-first];
        int i=first ,  j=d  ,k=0;

        while (i<d && j < n) {
            if (arr[i]<arr[j]) r[k]=arr[i++];
            else r[k]=arr[j++];
            ++k;
        };
        
        
        if (j < n) for ( ; j<n;++j) r[k++]=arr[j];
        else for ( ; i<d;++i) r[k++]=arr[i];

       for (k=first;k<n;++k) arr[k]=r[k-first];
}



} //