def swap (alist, i1, i2):
    temp = alist[i1]
    alist[i1] = alist[i2]
    alist[i2] = temp

def divide (alist, left, right):
    i = left
    j = right - 1
    pivot = alist[right]
    while (i < j):
	# search for an item greater than pivot on the left
	while ((alist[i] <= pivot) and (i < right)):
	    i += 1
	# search for an item smaller than pivot on the right
	while ((alist[j] >= pivot) and (j > left)):
	    j -= 1

	if (i < j):
	    # swap and continue
	    swap (alist, i, j)
	    j -= 1
	    i += 1
    # you may have to swap alist[i] with pivot if it is greater
    if (alist[i] > pivot):
	swap (alist, i, right)

    # return position of the pivot element
    return i

def quicksort (alist, left, right):
    if (left < right):
	index = divide (alist, left, right)
	quicksort (alist, left, index-1)
	quicksort (alist, index+1, right)


myList = [4,8,3,5,1,2,7,11,9,2]
print myList
quicksort (myList, 0, len(myList)-1)
print myList