# cython: language_level=3

"""Module provides nothing but a simple insertion sort."""

ifdef(`m4purepy',`@profile')
ifdef(`m4pyx',cp)def insertionsort(ifdef(`m4pyx',list )list_, ifdef(`m4pyx',unsigned int )left, ifdef(`m4pyx',unsigned int) right):
    """Perform an insertion sort on a subregion of a list."""
ifdef(`m4pyx',`    cdef unsigned int i')
    # this one doesn't like being an unsigned int
ifdef(`m4pyx',`    cdef int j')
    for i in range(left+1, right+1):
        j = i
        temp = list_[j]
        #while j > left and list_[j-1] > temp:
        #    list_[j] = list_[j-1]
        #    j -= 1
        while True:
            list_j_minus_1 = list_[j - 1]
            if j > left and list_j_minus_1 > temp:
                list_[j] = list_j_minus_1
                j -= 1
            else:
                break
        list_[j] = temp