def binary_search(arr, val, start, end):
	if start == end:
		if arr[start] > val:
			return start
		else:
			return start+1
	elif start > end:
		return start
	else: 
		mid = (start+end)/2
		if arr[mid] < val:
			return binary_search(arr, val, mid+1, end)
		elif arr[mid] > val:
			return binary_search(arr, val, start, mid-1)
		else: # arr[mid] = val
			return mid
			
def insertion_sort(arr):
    for i in xrange(1, len(arr)):
        val = arr[i]
        j = binary_search(arr, val, 0, i-1)
        arr = arr[:j] + [val] + arr[j:i] + arr[i+1:]
    return arr