Insertion sort with binary search in Python I have a bit of trouble simplifying the binary search code. This is different from the traditional binary search because we effectively want to find the location for which A[j] is the least element larger than the current unsorted value.

Thoughts?

def binary_search(A, value, start, end):
    # we need to distinugish whether we should insert
    # before or after the left boundary.
    # imagine [0] is the last step of the binary search
    # and we need to decide where to insert -1
    if start == end:
        if A[start] &gt; value:
            return start
        else:
            return start+1

    # this occurs if we are moving beyond left's boundary
    # meaning the left boundary is the least position to
    # find a number greater than value
    if start &gt; end:
        return start

    mid = (start+end)/2
    if A[mid] &lt; value:
        return binary_search(A, value, mid+1, end)
    elif A[mid] &gt; value:
        return binary_search(A, value, start, mid-1)
    else:
        return mid

def insertion_sort(A):
    for i in xrange(1, len(A)):
        value = A[i]
        j = binary_search(A, value, 0, i-1)
        A = A[:j] + [value] + A[j:i] + A[i+1:]
    return A

print insertion_sort([0,1,-1])
print insertion_sort([0,1,2,3,9,-1])
print insertion_sort([1,2,3,4,5,6,7,8,11,10,0])
Your binary_search is the same as the built-in function bisect.bisect, and you might find the implementation helpful to study.