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