def pick_pivot_i(A, from_i, to_i):
    return (to_i + from_i) // 2


def qsort_debug(A, from_i, to_i, depth=0):
    """ guess: A -> list(), [from_i, to_i] -> indexes in array"""

    print(depth * '|', "Quicksorting: ", A, from_i, to_i)
    print(depth * '|', "  actual data:", A[from_i:to_i + 1])

    if from_i >= to_i:
        print(depth * '|', "recursion ended")
        return

    pivot_i = pick_pivot_i(A, from_i, to_i)
    print(depth * '|', "pivot: ", A[pivot_i])

    # trick how to simplify qsort -> move pivot at the end of sequence, and compare with '<=', which makes sure that pivot will be swapped at A[j] at last cycle iteration
    # note: the side-effect is that same values as pivot, are going to end up in the 'left' part of the splitted array
    A[to_i], A[pivot_i] = A[pivot_i], A[to_i]

    print(depth * '|', "  actual data:", A[from_i:to_i + 1])
    # j is index where 'pivot' _should_ be
    # every item on index smaller than 'j' is smaller than pivot
    # every item on index bigger than 'j' is bigger than pivot
    j = from_i

    # debug lines, make code readable
    print(depth * '|', "-" * 50)

    for base_i in range(to_i - from_i + 1):
        i = from_i + base_i
        print(depth * '|', " j: ", j, "i: ", i)
        print(depth * '|', " smaller than pivot:", A[from_i:j])
        print(depth * '|', " bigger than pivot:", A[j:i])
        print(depth * '|', " processing:", A[i])
        print(depth * '|', " unprocessed:", A[i + 1:to_i + 1])
        if A[i] <= A[to_i]:
            print(depth * '|', " going to swap A[i], A[j] - ", A[i], ',', A[j])

            tmp = A[j]
            A[j] = A[i]
            A[i] = tmp

            j += 1

        # adding 'empty' line also makes the output more readable
        print(depth * '|')

    # last iteration of cycle have to be swap of pivot to place, so assertion that A[j] = pivot can hold, however cycle still increments j after it, we have to deicrement it
    j -= 1

    print(depth * '|', "-" * 50)

    print(depth * '|', "smaller than pivot:", A[from_i:j])
    print(depth * '|', "pivot:", A[j])
    print(depth * '|', "bigger than pivot:", A[j + 1:to_i])

    print(depth * '|')

    # should sort all values smaller than pivot
    qsort_debug(A, from_i, j - 1, depth + 1)
    # should sort all values bigger than pivot
    qsort_debug(A, j + 1, to_i, depth + 1)

    print(depth * '|')


# REMEMBER: this is what we want in your exams, not the debug version above, which has high complexity given the use of A[i:j] operator
def qsort(A, from_i, to_i):
    """ guess: A -> list(), [from_i, to_i] -> indexes in array, have to sort A[from_i - to_i]"""

    if from_i >= to_i:
        return

    pivot_i = pick_pivot_i(A, from_i, to_i)

    # trick how to simplify qsort -> move pivot at the end of sequence, and compare with '<=', which makes sure that pivot will be swapped at A[j] at last cycle iteration
    # note: the side-effect is that same values as pivot, are going to end up in the 'left' part of the splitted array
    A[to_i], A[pivot_i] = A[pivot_i], A[to_i] # this is nice python syntax how to swap items

    # j is index where 'pivot' _should_ be
    # every item on index smaller than 'j' is smaller than pivot
    # every item on index bigger than 'j' is bigger than pivot
    j = from_i

    for base_i in range(to_i - from_i + 1): # note that range(i), makes sequence [0,1,...,i-2,i-1], sometimes not what we want
        i = from_i + base_i

        if A[i] <= A[to_i]:
            tmp = A[j]
            A[j] = A[i]
            A[i] = tmp

            j += 1

    # last iteration of cycle have to be swap of pivot to place, so assertion that A[j] = pivot can hold, however cycle still increments j after it, we have to deicrement it
    j -= 1

    # should sort all values smaller than pivot
    qsort(A, from_i, j - 1)
    # should sort all values bigger than pivot
    qsort(A, j + 1, to_i)


qsort([], 0, 0)
qsort([1], 0, 0)
qsort([1, 2, 3, 4], 0, 3)
d = [8, 45, 9, 67, -42, 48, 53, 6, 97, 5, -666, 945, 0, 9, 43, 58, 3, 75]
qsort_debug(d, 0, len(d) - 1)