UNB/ CS/ David Bremner/ teaching/ java/ MergeSort.java
public class MergeSort
{
    /**
      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[] dest = new int[to-from+1];
        int aIndex=from;        int bIndex=mid+1;
        for (int destIndex=0;
             destIndex<dest.length; destIndex++){
            if(aIndex > mid)
                dest[destIndex]=a[bIndex++];
            else if (bIndex > to)
                dest[destIndex]=a[aIndex++];
            else if (a[aIndex] <= a[bIndex])
                dest[destIndex]=a[aIndex++];
            else
                dest[destIndex]=a[bIndex++];
        }
        for (int j = 0; j < dest.length; j++)
            a[from + j] = dest[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);

    }

}
//