// Implementation of Quick sort algorithm.
// Args:
//   	theArray:
//			is the array to sort
//
//		comparatorFn:
//			is a function object which is passed two elements (el1,el2) from 'array'
//			it should return 0 when el1 == el1, -1 when el1 < el2 and +1 when el1 > el2
//
// 		exchangerFn:
//			is a function object which is passed the array and two indices into the array to exchange
//
function	QuickSort( theArray, comparatorFn, exchangerFn )
{
	QuickSort_PartOfArray( theArray, comparatorFn, exchangerFn, 0, theArray.length - 1 );
}

// Quick sort part of an array.
function	QuickSort_PartOfArray( array, comparator, exchanger, first, last )
{
	if( first >= last )
		return;

	var	pivot_pos = QuickSort_DoPartitioning( array, comparator, exchanger, first, last );

	QuickSort_PartOfArray( array, comparator, exchanger, first, pivot_pos - 1 );
	QuickSort_PartOfArray( array, comparator, exchanger, pivot_pos + 1, last );
}

function	QuickSort_DoPartitioning( array, comparator, exchanger, first, last )
{
	var	piv_val = array[ first ];

	var	up = first, down = last;

	if( first >= last )
		return	first;

	while( true )
	{
		while( up < last && comparator( array[ up ], piv_val ) <= 0 )
			up++;

		while( down > first && comparator( array[ down ], piv_val ) > 0 )
			down--;

		if( up >= down )
		{
			exchanger( array, first, down );
			return down;
		}
		else
			exchanger( array, up, down );
	}
}