/*
 *  This code is from the book:
 *
 *    Winder, R and Roberts, G (2000) Developing Java
 *    Software, second edition, John Wiley & Sons.
 *
 *  It is copyright (c) 2000 Russel Winder and Graham Roberts.
 */

package ADS ;
import ADS.Comparator ;
/**
 *  Sort an array using Merge Sort.  This is an O(n.log(n)) sort.
 *
 *  @version 1.1 1999.11.27
 *  @author Russel Winder
 */
public class MergeSort {
  /**
   *  The sort operation.
   *
   *  @param a the array to be sorted.
   *  @param c the <CODE>Comparator</CODE> used to compare the
   *  <CODE>Object</CODE> during the sort process.
   */ 
  public static void sort(final Object[] a, final Comparator c) {
    if (a.length > 1) {
      //  Find the length of the data.  Arbitrarily split the data
      //  into two arrays by simply splitting in two.  Then
      //  recursively sort the two arrays and when that has happened
      //  merge the two arrays into a single result array.
      int xLength = (a.length-1)/2 + 1 ;
      int yLength = a.length - xLength ;
      Object[] x = new Object[xLength] ;
      Object[] y = new Object[yLength] ;
      System.arraycopy(a, 0, x, 0, xLength) ;
      System.arraycopy(a, xLength, y, 0, yLength) ;
      sort(x, c) ;
      sort(y, c) ;
      merge(a, x, y, c) ;
    }
  }
  /**
   *  Merge two source arrays which are pre-sorted to a target
   *  array.  The <CODE>Comparator</CODE> is used to select which
   *  element from the two queues to take next.
   *
   *  @param target the array into which to copy things.
   *  @param a one of the two source arrays.
   *  @param b the second of the two source arrays.
   *  @param c the <CODE>Comparator</CODE> used to compare the
   *  objects to determine the correct selection policy.
   */
  private static void merge(Object[] target,
                            Object[] a,
                            Object[] b,
                            Comparator c) {
    int t_index = 0 ;
    int a_index = 0 ;
    int b_index = 0 ;
    while (true) {
      //  The a array is used up so just copy the b array and
      //  finish.
      if (a_index >= a.length) {
        System.arraycopy(b,b_index,target,t_index,b.length-b_index) ;
        break ;
      }
      //  The b array is used up so just copy the a array and
      //  finish.
      if (b_index >= b.length) {
        System.arraycopy(a,a_index,target,t_index,a.length-a_index) ;
        break ;
      }
      //  Select the appropriate element from the two arrays and
      //  go to the next iteration.
      target[t_index++] = c.relation(a[a_index], b[b_index])
       ? a[a_index++]
       : b[b_index++] ;
    }
  }
}