# 3 = 2^2
# x = 2

def qsort(arr):
    print(arr)
    if len(arr) == 0:
        return arr

    pivot = arr[0]
    sup_arr = []
    inf_arr = []
    arr.remove(pivot)
    for n in arr:
        print('iter')
        if n > pivot:
            sup_arr.append(n)
        else:
            inf_arr.append(n)
    return qsort(inf_arr) + [pivot] + qsort(sup_arr)


#assert qsort([1]) == [1]
#assert qsort([2, 1]) == [1, 2]
#assert qsort([3, 2, 1]) == [1, 2, 3]
qsort([1, 2, 3])