# -*- coding: utf-8 -*-
from __future__ import absolute_import
import sys

try:
    pass
except ImportError:
    pass


def shell_sort(array, left=None, right=None):
    lo = 0 if not left else left
    hi = len(array) - 1 if not right else right
    array = array[lo:hi]

    def swap(i, k):
        array[i], array[k] = array[k], array[i]

    length = len(array)
    gap = length // 2
    while gap > 0:
        # insertion sort for each group
        for j in range(gap, length):
            i = j
            while (i - gap) >= 0:
                if array[i] < array[i - gap]:
                    swap(i, i - gap)
                    i -= gap
                else:
                    break
        gap = gap // 2
    return array

if __name__ == '__main__':
    a =  [80, 93, 60, 12, 42, 30, 68, 85, 10]
    print(shell_sort(a))