// (c) MIT 2003.  All rights reserved.

////////////////////////////////////////////////////////////////////////////////
//
// FILE:	QuickSort.java
//
// AUTHOR:	Manoj D. Muzumdar
//		archon@ai.mit.edu
//
// DATE:	July, 1998
//
// COPYRIGHT:	Massachusetts Institute of Technology
//		All rights reserved.
//
// PURPOSE:     Quicksort implementation
//
////////////////////////////////////////////////////////////////////////////////

package rec.util;

import java.lang.reflect.*;
import java.util.Comparator;

public final class QuickSort
{
  /*
   * Main sort routine;
   *
   * If a is an array of primitive types, cmp.compare() will be
   *     called with the appropriate wrapper.
   */
  public static void sort( Object a, Comparator cmp )
  {
    sort( a, 0, Array.getLength( a ) - 1, cmp );
  }

  //////////////////////////////////////////////////////////////////////////////

  /**
   * Recursive routine.
   */
  private static void sort( Object a, int lo0, int hi0,
			    Comparator cmp )
  {
    int lo = lo0;
    int hi = hi0;
    Object mid = null;

    if( hi0 > lo0 ) {

      mid = Array.get( a, (lo0 + hi0) / 2 );

      // Loop through the array until indices cross.
      while( lo <= hi ) {
	while( lo < hi0
	       && cmp.compare( Array.get( a, lo ), mid ) < 0 ) {
	  ++lo;
	}

	while( hi > lo0
	       && cmp.compare( Array.get( a, hi ), mid ) > 0 ) {
	  --hi;
	}

	// if the indexes have not crossed, swap
	if( lo <= hi ) {
	  swap( a, lo, hi );
	  ++lo;
	  --hi;
	}
      }

      if(lo0 < hi) {
	sort( a, lo0, hi, cmp );
      }

      if( lo < hi0 ) {
	sort( a, lo, hi0, cmp );
      }
    }
  }

  /**
   * Swaps a[i] and a[j].
   */
  private static void swap( Object a, int i, int j )
  {
    Object t = Array.get( a, i );
    Array.set( a, i, Array.get( a, j ) );
    Array.set( a, j, t );
  }
}

////////////////////////////////////////////////////////////////////////////////
