import random

def insert_sort_gap(li,gap):
    for i in range(gap,len(li)):
        tmp = li[i]
        j = i - gap
        while j >= 0 and li[j] > tmp:
            li[j+gap] = li[j]
            j -= gap
        li[j+gap] = tmp

def shell_sort(li):
    d = len(li) // 2
    while d >= 1:
        insert_sort_gap(li,d)
        d = d // 2

def main():
    li = list(range(1000))
    random.shuffle(li)
    shell_sort(li)
    print(li)

if __name__ == '__main__':
    main()