In [60]:

    

def sort(seq):
    if len(seq) <= 1:
        return seq
    else:
        pivot = seq[0]
        left, right = [], []
        for x in seq[1:]:
            if x < pivot:
                left.append(x)
            else:
                right.append(x)
        return sort(left) + [pivot] + sort(right)


    

In [61]:

    

sort([3,2,1])


    

    
Out[61]:





[1, 2, 3]

In [62]:

    

def patition(seq, low, high):
    current = low
    for i in range(low, high):
        if seq[i] < seq[high]:
            temp = seq[i]
            seq[i] = seq[current]
            seq[current] = temp
            current += 1
        
    temp = seq[high]
    seq[high] = seq[current]
    seq[current] = temp
    
    return current


    

In [63]:

    

def sort_inplace(seq, low, high):
    if low < high:
        p = patition(seq, low, high)
        sort_inplace(seq, low, p-1)
        sort_inplace(seq, p+1, high)
        return seq


    

In [64]:

    

seq = [10,3,1]


    

In [65]:

    

print(sort_inplace(seq, 0, 2))


    

    




[1, 3, 10]

In [67]:

    

def sort_new(seq):
    if len(seq) <= 1:
        return seq
    
    pivot = seq[0]
    left, right = [], []
    for x in seq[1:]:
        if x < pivot:
            left.append(x)
        else:
            right.append(x)
    
    return sort(left) + [pivot] + sort(right)


    

In [68]:

    

sort_new([3,2,1])


    

    
Out[68]:





[1, 2, 3]

In [ ]: