#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013

def sort(x) :
    sortaux(x, 1)
    quit()
    step = len(x)//2
    while step>1 :
        print(step)
        sortaux(x, step)
        step = step//2

def sortaux(x, step) :
    for i in range(step, len(x)) :
        # everything to the left of position i is sorted!
        minv = x[i]
        j = i-step
        while j>=0 and x[j]>minv :
            print("x")
            x[j+step] = x[j]
            j -= step
        x[j+step] = minv
        print(x[:i+1], x[i+1:])
    return x

y = [31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27, 9]
sort(y)
print("ans:", y)