"""Implement quick sort in Python.
Input a list.
Output a sorted list."""
def quicksort(array):
    if len(array) >1:
        print "enter array", array
        pivot = len(array) - 1
        print "pivot", array[pivot]
        x = 0
        while x < pivot:
            if array[x]>array[pivot]:
                piv = array[pivot]
                xval = array[x]
                array[x] = array[pivot-1]
                array[pivot] = xval
                array[pivot-1] = piv
        #        temp = array[x]
         #       array[x] = array[pivot]
         #       array[pivot] = temp
               # array.append(array.pop(x))
                pivot -= 1
            else:
                x += 1
        print "pre recur split array", array
        print "left", array[:pivot]
        print "right", array[pivot+1:]
        quicksort(array[:pivot])
        quicksort(array[pivot+1:])
        print "post recur split array", array
    return array
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
#test = [21, 4, 1, 3]
print quicksort(test)
print "answer", test

enter array [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
pivot 14
pre recur split array [6, 4, 1, 3, 9, 14, 25, 20, 21, 21]
left [6, 4, 1, 3, 9]
right [25, 20, 21, 21]
enter array [6, 4, 1, 3, 9]
pivot 9
pre recur split array [6, 4, 1, 3, 9]
left [6, 4, 1, 3]
right []
enter array [6, 4, 1, 3]
pivot 3
pre recur split array [1, 3, 4, 6]
left [1]
right [4, 6]
enter array [4, 6]
pivot 6
pre recur split array [4, 6]
left [4]
right []
post recur split array [4, 6]
post recur split array [1, 3, 4, 6]
post recur split array [6, 4, 1, 3, 9]
enter array [25, 20, 21, 21]
pivot 21
pre recur split array [21, 20, 21, 25]
left [21, 20]
right [25]
enter array [21, 20]
pivot 20
pre recur split array [20, 21]
left []
right [21]
post recur split array [20, 21]
post recur split array [21, 20, 21, 25]
post recur split array [6, 4, 1, 3, 9, 14, 25, 20, 21, 21]
[6, 4, 1, 3, 9, 14, 25, 20, 21, 21]
answer [6, 4, 1, 3, 9, 14, 25, 20, 21, 21]