///////
//
// Student: Russell Lowke
//     T.F: Francis Crick
// Unit Seven, pencil-and-paper - question 2 [worth 2pts],  7/30/2002
//
//  Write a recursive version of the procedure sift() that is used in heapsort,
//  without using a break statement.
//


//
// swap - swap the values of two variables.
// Used by several of the sorting algorithms below.
//
template <class elt>
void swap(elt& a, elt& b)
{
    elt temp;
    temp = a;
    a = b;
    b = temp;
}


//
// recursive sift function
//
void sift(int array[], int start, int end)
{
	int item, leftPos, rightPos, childPos;
	
	leftPos    = ( start * 2     > end ? -1 : start * 2 );
	rightPos   = ( start * 2 + 1 > end ? -1 : start * 2 + 1);
	
	// default to left child
	childPos   = leftPos;
	
	// if left child empty use right child
	if (leftPos == -1) {
		childPos = rightPos;
	}
	
	// If right larger than left, use right
	if ( (leftPos > -1 && rightPos > -1) && array[rightPos] > array[leftPos] ) {
		childPos = rightPos;
	}

	// check if at end of tree, or sorted
	if (childPos == -1 || array[start] > array[childPos]) {
		// finished;
	} else {

		// assuming tree was previously sorted
		swap(array[start], array[childPos]);		// swap
		sift(array, childPos, end);					// sift down
	}
}