abstract class QuicksortTemplate
{

	public static function Sort( items : ref< array< Variant > >, comparator : SortComparatorTemplate, leftIndex : Int32, rightIndex : Int32 )
	{
		var index : Int32;
		if( items.Size() > 1 )
		{
			index = Partition( items, comparator, leftIndex, rightIndex );
			if( leftIndex < ( index - 1 ) )
			{
				Sort( items, comparator, leftIndex, index - 1 );
			}
			if( index < rightIndex )
			{
				Sort( items, comparator, index, rightIndex );
			}
		}
	}

	private static function Partition( items : ref< array< Variant > >, comparator : SortComparatorTemplate, leftIndex : Int32, rightIndex : Int32 ) : Int32
	{
		var i, j : Int32;
		var pivot : Variant;
		var tempItem : Variant;
		i = leftIndex;
		j = rightIndex;
		pivot = items[ FloorF( ( ( Float )( rightIndex ) ) + ( ( ( Float )( leftIndex ) ) / 2.0 ) ) ];
		while( i <= j )
		{
			while( comparator.Compare( items[ i ], pivot ) )
			{
				i += 1;
			}
			while( !( comparator.Compare( items[ j ], pivot ) ) )
			{
				j -= 1;
			}
			if( i <= j )
			{
				tempItem = items[ i ];
				items[ i ] = items[ j ];
				items[ j ] = tempItem;
				i += 1;
				j -= 1;
			}
		}
		return i;
	}

}

abstract class SortComparatorTemplate
{

	public virtual function Compare( left : Variant, right : Variant ) : Bool
	{
		return false;
	}

}

class QuicksortInt
{

	public static function Sort( items : ref< array< Int32 > >, comparator : IntComparator, leftIndex : Int32, rightIndex : Int32 )
	{
		var index : Int32;
		if( items.Size() > 1 )
		{
			index = Partition( items, comparator, leftIndex, rightIndex );
			if( leftIndex < ( index - 1 ) )
			{
				Sort( items, comparator, leftIndex, index - 1 );
			}
			if( index < rightIndex )
			{
				Sort( items, comparator, index, rightIndex );
			}
		}
	}

	private static function Partition( items : ref< array< Int32 > >, comparator : IntComparator, leftIndex : Int32, rightIndex : Int32 ) : Int32
	{
		var i, j : Int32;
		var pivot : Int32;
		var tempItem : Int32;
		i = leftIndex;
		j = rightIndex;
		pivot = items[ FloorF( ( ( ( Float )( rightIndex ) ) + ( ( Float )( leftIndex ) ) ) / 2.0 ) ];
		while( i <= j )
		{
			while( comparator.Compare( items[ i ], pivot ) > 0 )
			{
				i += 1;
			}
			while( comparator.Compare( items[ j ], pivot ) < 0 )
			{
				j -= 1;
			}
			if( i <= j )
			{
				tempItem = items[ i ];
				items[ i ] = items[ j ];
				items[ j ] = tempItem;
				i += 1;
				j -= 1;
			}
		}
		return i;
	}

}

class IntComparator
{

	public virtual function Compare( left : Int32, right : Int32 ) : Int32
	{
		if( left == right )
		{
			return 0;
		}
		return ( ( left < right ) ? ( 1 ) : ( -1 ) );
	}

}

class QuicksortInventoryItemData
{

	public static function Sort( items : ref< array< InventoryItemData > >, comparator : InventoryItemDataComparator, leftIndex : Int32, rightIndex : Int32 )
	{
		var index : Int32;
		if( items.Size() > 1 )
		{
			index = Partition( items, comparator, leftIndex, rightIndex );
			if( leftIndex < ( index - 1 ) )
			{
				Sort( items, comparator, leftIndex, index - 1 );
			}
			if( index < rightIndex )
			{
				Sort( items, comparator, index, rightIndex );
			}
		}
	}

	private static function Partition( items : ref< array< InventoryItemData > >, comparator : InventoryItemDataComparator, leftIndex : Int32, rightIndex : Int32 ) : Int32
	{
		var i, j : Int32;
		var pivot : InventoryItemData;
		var tempItem : InventoryItemData;
		i = leftIndex;
		j = rightIndex;
		pivot = items[ FloorF( ( ( ( Float )( rightIndex ) ) + ( ( Float )( leftIndex ) ) ) / 2.0 ) ];
		while( i <= j )
		{
			while( comparator.Compare( items[ i ], pivot ) > 0 )
			{
				i += 1;
			}
			while( comparator.Compare( items[ j ], pivot ) < 0 )
			{
				j -= 1;
			}
			if( i <= j )
			{
				tempItem = items[ i ];
				items[ i ] = items[ j ];
				items[ j ] = tempItem;
				i += 1;
				j -= 1;
			}
		}
		return i;
	}

}

class InventoryItemDataComparator
{

	public virtual function Compare( const left : ref< InventoryItemData >, const right : ref< InventoryItemData > ) : Int32
	{
		return 0;
	}

}

