from random import randint

def melange(t):
    for i in range(1, len(t)):
        j = randint(0, i)
        t[i], t[j] = t[j], t[i]

def partition(t, g, d):
    assert 0 <= g and g < d-1 and d <= len(t)
    pivot = t[g]
    m = g
    for i in range(g+1, d):
        if t[i] < pivot:
            m += 1
            t[i], t[m] = t[m], t[i]
    t[g], t[m] = t[m], t[g]
    return m

def quickrec(t, g, d):
    """trie t[d..d[ avec le tri rapide"""
    if d <= g+1: return
    m = partition(t, g, d)
    quickrec(t, g  , m)
    quickrec(t, m+1, d)

def quicksort(t):
    melange(t)
    quickrec(t, 0, len(t))

### tests ############################################################

def est_trie(t):
    """teste si le tableau t est trié"""
    for i in range(0, len(t) - 1):
        if t[i] > t[i+1]:
            return False
    return True

n = 1
while n < 100_000:
    t = [randint(-n, n) for _ in range(n)]
    quicksort(t)
    assert est_trie(t)
    n *= 2