def tri_par_insertion(T):
     N = len(T)
     for k in range(1,N):
        tmp = T[k]
        i = k
        while i > 0 and tmp < T[i-1]:
           T[i] = T[i-1]
           i -= 1
        T[i] = tmp

def tri_de_shell(T):
    N = len(T)
    h = 1
    while h*3 < N:
        h = 3*h+1
        
    while h >= 1:
        for j in range(1,N):
            tmp = T[j]
            i = j
            while i > h-1 and tmp < T[i-h]:
                T[i] = T[i-h]
                i -= h
            T[i] = tmp
        h = h//3