Shell Sort

shell_sort.py

"""
Shell Sort
"""


def shell_sort(array):
    length = len(array)
    gap = length / 2

    while gap > 0:
        i = 0
        while i < length:
            min_index = i
            j = i
            while j < length:
                if array[j] < array[min_index]:
                    min_index = j
                j += gap
            if i != min_index:
                array[i], array[min_index] = array[min_index], array[i]
            i += gap
        gap /= 2
    return array


if __name__ == "__main__":
    array = [7, 5, 3, 1, 2, 6, 4, 10, 9]
    print shell_sort(array)