qsort.py

def sort(list):
    if list = 空:
         return list
    left = list の左半分         ## O(N)
    right = list の右半分        ## O(N)
    left = sort(left)            ## F(N/2)
    right = sort(right)          ## F(N/2)
    return combine(left, right)  ## C(N)

def combine(lista, listb):
    if lista = 空:
        return listb             ##O(1)
    if listb = 空:
        return lista             ##O(1)
    if lista[0] < listb[0]:
        return lista[0] + combine(lista[1:], listb)  ##C(A-1+B) + 1
    else:
        return listb[0] + combine(lista, listb[1:])  ##C(A+B-1) + 1