#---------------------------------------------------
# Function name:  split
#   Purpose:  
#   Input:    list -> the array of sorted elements
#             first -> the index of the first element in the
#                  section of array list to be split
#             last -> the index of the last element in the
#                  section of array list to be split
#   Output:   the array, list, with the elements less than list[first] on the left half
#                 of the sub-array, and the elements greater than list[first] on
#                 the right half of the sub-array
#             the index of the split value in array list

def split (list, first, last):
	left = first + 1
	right = last

	while (left <= right):
		while ((left <= right) and (list[left] < list[first])):
			left = left + 1
		while ((left <= right) and (list[right] > list[first])):
			right = right - 1

		if (left < right):
			temp = list[left]
			list[left] = list[right]
			list[right] = temp

	splitPoint = right

	temp = list[first]
	list[first] = list[splitPoint]
	list[splitPoint] = temp

	return splitPoint
	

#---------------------------------------------------
# Function name:  quickSort
#   Purpose:  sorts an array by recursively splitting and quick sorting the
#                 upper and lower halves of the split sub-arrays
#   Input:    list -> the array of unsorted elements
#             first -> the index of the first element in the
#                  section of array list to be sorted
#             last -> the index of the last element in the
#                  section of array list to be sorted
#   Output:  the sorted array, list

def quickSort (list, first, last):
	if (first < last):
		splitPoint = split (list, first, last)

		list = quickSort (list, first, splitPoint-1)
		list = quickSort (list, splitPoint+1, last)

	return list


#---------------------------------------------------
# Main program:
#

names = ["Sue", "Mark", "William", "Cora", "Beth", "Tyler", "Ann", "June", "David"]

print names
print

names = quickSort (names, 0, (len(names)-1))

print names