import random


def quicksort(l, _begin=0, _end=None):
    if _end is None:
        _end = len(l) - 1
    assert _begin < _end, (_begin, _end)
    print(f"{l=} {_begin=} {_end}")

    pivot = (l[_begin] + l[_end]) / 2
    done_on_begin = _begin
    done_on_end = _end

    while done_on_begin < done_on_end:
        if l[done_on_begin] > pivot:
            l[done_on_begin], l[done_on_end] = l[done_on_end], l[done_on_begin]
            done_on_end -= 1
        else:
            done_on_begin += 1
        print(f"  {l[_begin:done_on_begin]=} | {pivot=} | {l[done_on_end+1:_end]=}")

    # Nyní je:
    #  * vše begin - done_on_begin menší, než pivot
    #  * vše done_on_end - end větší, než pivot

    if _begin < done_on_begin - 1:
        quicksort(l, _begin, done_on_begin - 1)

    if done_on_end + 1 < _end:
        quicksort(l, done_on_end + 1, _end)

    return l


# l = [7, 0, 3, 2, 8, 5, 1, 6, 4, 9]  # Tento funguje
l = [3, 5, 8, 0, 4, 6, 7, 1, 9, 2] # Tento ale nefunguje!

print("Vstupni list:", l)
quicksort(l)
print("Serazeny list:", l)

assert l == sorted(l), l

# Kód pro zkoušení náhodných listů:

# for _ in range(100):
#     l = list(range(10))
#     random.shuffle(l)
#     print("l ------", l)
#     quicksort(l)
#     assert l != sorted(l), l