public class MergeSort3
{
    /**
      Merges two adjacent subranges of an array
      @param a the array with entries to be merged
      @param from the index of the first element of the
         first range
      @param mid the index of the last element of the
         first range
      @param to the index of the last element of the
         second range
   */
   public static void merge(int[] a,
      int from, int mid, int to)
   {  int n = to - from + 1;         // size of the range to be merged

      int[] b = new int[n]; // merge both halves into a temporary array b

      int i1 = from;         // next element to consider in the first range
      int i2 = mid + 1;      // next element to consider in the second range
      int j = 0;             // next open position in b

      // as long as neither i1 nor i2 past the end, move the smaller into b
      while (i1 <= mid && i2 <= to)
      {  if (a[i1] < a[i2])
         {  b[j] = a[i1];
            i1++;
         }
         else
         {  b[j] = a[i2];
            i2++;
         }
         j++;
      }

      // note that only one of the two while loops
      // below is executed

      // copy any remaining entries of the first half
      while (i1 <= mid)
      {  b[j] = a[i1];
         i1++;
         j++;
      }

      // copy any remaining entries of the second half
      while (i2 <= to) {
          b[j] = a[i2];
          i2++;
          j++;
      }

      // copy back from the temporary array
      for (j = 0; j < n; j++)
          a[from + j] = b[j];
   }
    //
    /**
       Sorts a range of an array, using the merge sort
       algorithm.
       @param a the array to sort
       @param from the first index of the range to sort
       @param to the last index of the range to sort
    */
    public static void mergeSort(int[] a, int from,
                                 int to){
        if (from == to) return;
        int mid = (from + to) / 2;

        mergeSort(a, from, mid);
        mergeSort(a, mid + 1, to);

        merge(a, from, mid, to);
    }
   /**
      Sorts an array, using the merge sort algorithm.
      @param a the array to sort
   */
   public static void sort(int[] a)
   {  mergeSort(a, 0, a.length - 1);
   }

    public static void main(String[] args){
        int [] data= ArrayUtil.randomIntArray(10,1000);

        ArrayUtil.print(data);

        sort(data);

        ArrayUtil.print(data);

    }

}
//