'''Module provides a binarysort'''

ifdef(`m4purepy',`@profile')
ifdef(`m4pyx',cp)def binarysort(ifdef(`m4pyx',list )list_, ifdef(`m4pyx',unsigned int )initial_left, ifdef(`m4pyx',unsigned int )initial_right):
	ifdef(`m4pyx', cdef unsigned int left)
	ifdef(`m4pyx', cdef unsigned int left_for_binary_search)
	ifdef(`m4pyx', cdef unsigned int right_for_binary_search)

	'''
	Sort a (small) list using binary sort.  It's much like insertion sort, except we use a binary search
	on the already-sorted portion to find where things should be placed.

	We use a temporary list for speed.  This appears to be quite a bit faster than sticking to a single
	list.
	'''

	new_list = []

	if initial_right > initial_left:
		new_list.append(list_[initial_left])

	for pivot in list_[initial_left + 1:]:
		new_list_len_minus_1 = `len'(new_list) - 1

		left_for_binary_search = 0
		right_for_binary_search = new_list_len_minus_1

		assert left_for_binary_search <= right_for_binary_search

		while left_for_binary_search < right_for_binary_search:
			midpoint = (left_for_binary_search + right_for_binary_search) / 2
			if pivot < new_list[midpoint]:
				right_for_binary_search = midpoint
			else:
				left_for_binary_search = midpoint + 1

		assert left_for_binary_search == right_for_binary_search

		if new_list[left_for_binary_search] < pivot:
			# we are >=
			new_list.insert(left_for_binary_search + 1, pivot)
		else:
			# we are <, insert before
			new_list.insert(left_for_binary_search, pivot)

	# now copy to the original list
	for index, value in enumerate(new_list):
		list_[initial_left + index] = value