def quick_sort_inplace(L):
    """Perform an in-place quicksort of the list L."""
    
    # used for finding random numbers
    from random import Random
    rand = Random()
    
    # simple counter
    ops = [0,]
    
    def divide(low, high):
        """Divide the current list/partition into more partitions."""
        if high > low:
            
            # pick a random pivot
            p = rand.randrange(low, high+1)
            
            # conquer this partition with that pivot
            p = conquer(low, high, p)
            
            # divide the conquered partition around the pivot
            divide(low, p-1)
            divide(p+1, high)
    
    def conquer(low, high, p):
        """Given a partition of the list, swap elements into a semi-sorted
           order around the pivot."""
        
        # first, move the pivot to the end of the partition
        pivot = L[p]
        L[p], L[high] = L[high], L[p]
        
        i = low # an element to swap
        j = low # where we are in the list
        
        # go over the elements in this partition
        while low <= j < high:
            ops[0] = ops[0]+1
            
            # we've found a number <= the pivot, lets swap it with itself or
            # the last found number greate than the pivot. j will be > than i,
            # and this if moves ignores numbers > than the pivot, and so i will
            # stop at the first number greater than the pivot, and i will stop
            # at the first number <= to the pivot.
            if L[j] <= pivot:
                L[i], L[j] = L[j], L[i]
                i = i+1
            
            # move along in the list
            j = j+1
        
        # swap the pivot out from the last position and into where the last
        # number greater than the pivot was found
        L[i], L[high] = L[high], L[i]
        
        # return the new pivot index
        return i
    
    # sort the list
    divide(0, len(L)-1)
    
    print "number of operations:", ops[0]

if __name__ == "__main__":
    ls = [5, 8, 3, 1, 2, 99, 14, 7]
    print "unsorted:", ls   
    quick_sort_inplace(ls)
    print "sorted:", ls