# Shell Sort: O(n^2)

def shell_sort(array):
    """Shell sort using Shell's (original) gap sequence: n/2, n/4, ..., 1.
    """
    gap = len(array) // 2
    # loop over the gaps
    while gap > 0:
        # do the insertion sort
        for i in range(gap, len(array)):
            val = array[i]
            j = i
            while j >= gap and array[j - gap] > val:
                array[j] = array[j - gap]
                j -= gap
            array[j] = val
        gap //= 2


if __name__ == "__main__":
    array = [17, 9, 13, 8, 7, -5, 6, 11, 3, 4, 1, 2]
    shell_sort(array)
    print(array)
