qsort.py

mylist = [1, 4, 6, 2, 5, 1, 4, 5, 5, 59, 3, 4, 5]

def move_to(v, oldi, newi):
    tmp = v[oldi]
    del v[oldi]
    v.insert(newi, tmp)


def qsort(v):
    pivot_index = len(v)
    pivot = v[-1]
    num_swaps = 0
    index = 0
    mid = len(v) #index of equal partition
    hi = len(v) #index of greater than partition
    while index < len(v)-num_swaps:
        elem = v[index]
        if elem > pivot:
            move_to(v, index, pivot_index)
            pivot_index -= 1
            num_swaps += 1
            hi -= 1
        elif elem == pivot:
            move_to(v, index, pivot_index-1)
            mid -= 1
            num_swaps += 1
        else:
            index += 1
    if mid > 0:
        v[:mid] = qsort(v[:mid])
    if hi < len(v):
        v[hi:] = qsort(v[hi:])
    return v