#coding:utf-8

'''
email: chenyan@feling.net

快速排序（原地排序，归并没办法原地，只能返回新的序列）
invented by Tony Hoare 1962
'''

def partition(l, begin, end):
    x = l[begin]
    i = begin
    for j in range(begin+1, end):
        if l[j]<=x:
            i += 1
            l[i], l[j] = l[j], l[i]
    l[i], l[begin] = l[begin], l[i]
    return i

def quicksort(l, begin=0, end=-9):
    '''
    >>> l = [0, 3, 2, 2, 5, 8, 2, 1, 4, 6, 7]
    >>> quicksort(l)    
    >>> l
    [0, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8]
    '''
    if end==-9:
        end = len(l)
    if begin<end:
        i = partition(l, begin, end)
        quicksort(l, begin, i)
        quicksort(l, i+1, end)

if __name__=='__main__':
    import doctest
    doctest.testmod()