'''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 xrange(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