UNB/ CS/ David Bremner/ teaching/ old/ cs1083/ 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 i=0; i<dest.length; i++){
            if(aIndex > mid) dest[i]=a[bIndex++];
            else if (bIndex > to) dest[i]=a[aIndex++];
            else if (a[aIndex] <= a[bIndex])
                dest[i]=a[aIndex++];
            else dest[i]=a[bIndex++];
        }
        System.arraycopy(dest,0,a,from,dest.length);
    }
    //
    /**
       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(100,1000);

        ArrayUtil.print(data);

        sort(data);

        ArrayUtil.print(data);

    }

}
//