Heap Sort

HeapSort.java

public class HeapSort {

	/*heapsort
	Description: Performs a heap sort on a given list

	Parameters: 
			int[] list: array of integers to be sorted	
	Pre: Initialized array      
	Post: Sorted array
	Returns:  Sorted array
	Called by: Any
	Calls:   None
	*/
	public static int[] heapsort( int[] test)
	{
		int i ,f, s;
		
		if( test.length == 0)
			return null;
		
		for( i = 1; i < test.length; i++)
		{
			int elt = test[i];
			s = i;
			f = (s -1) / 2;
			while( s > 0 && test[f] < elt)
			{
				test[s] = test[f];
				s = f;
				f = (s-1) / 2;
			}
			test[s] = elt;
		}
		
		for(i = test.length-1; i > 0; i--)
		{
			int iValue = test[i];
			test[i] = test[0];
			f = 0;
			if( i == 1)
				s = -1;
			else
				s = 1;
			if( i > 2 && test[2] > test[1] )
				s = 2;
			while( s >= 0 && iValue < test[s] )
			{
				test[f] = test[s];
				f = s;
				s = 2 * f + 1;
				if( s + 1 <= i - 1 && test[s] < test[s+1])
					s = s + 1;
				if( s > i - 1)
					s = -1;
			}
			test[f] = iValue;
		}
		return test;
	}
}