# cython: language_level=3

"""Module provides a shell sort function."""

ifdef(`m4pyx',cp)def shellsort(ifdef(`m4pyx',list )list_):
    """Shell sort function."""
ifdef(`m4pyx',`    cdef unsigned int size')
ifdef(`m4pyx',`    cdef unsigned int hmax')
ifdef(`m4pyx',`    cdef unsigned int haych')
ifdef(`m4pyx',`    cdef unsigned int i')
ifdef(`m4pyx',`    cdef unsigned int j')
ifdef(`m4pyx',`    cdef object value')
    size = `len'(list_)
    hmax = size // 9

    haych = 1
    while haych <= hmax:
        haych = haych * 3 + 1

    while haych > 0:
        for i in range(haych, size):
            value = list_[i]
            j = i
            while j >= haych and value < list_[j-haych]:
                list_[j] = list_[j-haych]
                j -= haych
            list_[j] = value
        haych = haych // 3