#!/usr/bin/python

def partition(alist, first, last):
	pivotvalue = alist[first]

	leftmark, rightmark = first+1, last

	done = False
	while not done:
		while leftmark <= rightmark and \
				alist[leftmark] < pivotvalue:
			leftmark = leftmark + 1
		while alist[rightmark] > pivotvalue and \
				rightmark >= leftmark:
			rightmark = rightmark -1
		if rightmark < leftmark:
			done = True
		else:
			alist[leftmark],alist[rightmark]= \
				alist[rightmark],alist[leftmark]

	alist[first],alist[rightmark]= \
		alist[rightmark],alist[first]

	return rightmark

def quickSort(alist):
	quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
	if first < last:
		splitpoint = partition(alist,first,last)

		quickSortHelper(alist,first,splitpoint-1)
		quickSortHelper(alist,splitpoint+1,last)

def medyan(alist):
	if len(alist) % 2 == 1:
		return alist[int(len(alist) / 2)]
	else:
		i = int(len(alist) / 2)
		return (alist[i] + alist[i-1]) / 2

alist = [1,3,2,8,6,15,54,31, 0]
quickSort(alist)
print(alist)
print(medyan(alist))