/******************************************************************************
Mergesort
----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.

Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted. 
*******************************************************************************/

package FlexOr.searchAndSort;
import FlexOr.container.*;

/** Sort an array of objects using mergesort.

<P>
@author Gunnar Gotshalks
@version 1.0 1999 Jan 15
*/

public class MergeSort implements ArraySort {

/**
@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
  public void sort(final Object[] array, final BinaryPredicate bp) {
      execute(array, bp);
  }

/** The mergesort method.  Merge sort requires scratch space the same size as
the array to sort which is used to merge subarrays.

@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
  public static void execute(final Object[] array, final BinaryPredicate bp) {
    if (array.length > 1) 
        mergesort(false, array, new Object [array.length],
                  0, array.length-1, bp);
  }

  //Loop invariant: ???

  private static void mergesort(final boolean transfer,
                         final Object[] array,
                         final Object[] mergeSpace,
                         final int lowerIndex, final int upperIndex,
                         final BinaryPredicate bp) {
      if (lowerIndex == upperIndex) {
        if (transfer) { mergeSpace[lowerIndex] = array[lowerIndex]; }
        return;
      }
      int mid = (lowerIndex + upperIndex)/2;
      mergesort(!transfer, array, mergeSpace, lowerIndex, mid, bp);
      mergesort(!transfer, array, mergeSpace, mid+1, upperIndex, bp);
      if (transfer)
          merge(array, mergeSpace, lowerIndex, mid, mid+1, upperIndex,bp);
      else
          merge(mergeSpace, array, lowerIndex, mid, mid+1, upperIndex, bp);
  }

/******************************************************************************
Merge from[lowerIndex1 .. upperIndex1] with from[lowerIndex2 .. upperIndex2]
into to[lowerIndex .. upperIndex].
*/

  private static void merge(final Object[] from,
                     final Object[] to,
                     final int lowerIndex1, final int upperIndex1,
                     final int lowerIndex2, final int upperIndex2,
                     final BinaryPredicate bp) {

    int i = lowerIndex1; // works through from[lowerIndex1 .. upperIndex1]
    int j = lowerIndex2; // works through from[lowerIndex2 .. upperIndex2]
    int k = lowerIndex1; // works through to[lowerIndex1 .. upperIndex2]
    
    while (i <= upperIndex1 && j <= upperIndex2) {
      if (bp.execute(from[i], from[j])) { to[k] = from[i]; i++; }
      else { to[k] = from[j]; j++; }
      k++;
    }
    while (i <= upperIndex1) { to[k] = from[i]; i++; k++; }
    while (j <= upperIndex2) { to[k] = from[j]; j++; k++; }
  }
}