Insertion sort based on binary search

insertion_sort_with_binary_search.py

def find_index(x, v, left=0, right=None):
    # Set `right` to a proper value for the first iteration
    if right is None:
        right = len(x)

    while left < right:
        mid = (left+right) // 2
        if v < x[mid]:
            right = mid
        else:
            left = mid+1

    return left


def insertion_sort(x):
    for i in range(1, len(x)):
        # Find index within `x[0]` and `x[i]` where to insert element `x[i]`
        index = find_index(x, x[i], right=i)
        # Remove index `i` from `x`, retaining its value
        value = x.pop(i)
        # Insert `value` back to `x` at the found `index`
        x.insert(index, value)


if __name__ == '__main__':
    print 'find_index() examples'
    print '---------------------'
    print '1 fits in [1, 3, 5, 7, 9] at index: ', find_index([1, 3, 5, 7, 9], 1)
    print '5 fits in [1, 3, 5, 7, 9] at index: ', find_index([1, 3, 5, 7, 9], 5)
    print '9 fits in [1, 3, 5, 7, 9] at index: ', find_index([1, 3, 5, 7, 9], 9)
    print '8 fits in [1, 3, 5, 7, 9] at index: ', find_index([1, 3, 5, 7, 9], 8)
    print ''

    print 'insertion_sort() examples'
    print '-------------------------'
    l1 = [1, 4, 2, 3]
    print l1, ' becomes...'
    insertion_sort(l1)
    print '... ', l1, ' after sorting'
    l2 = [4, 3, 2, 1]
    print l2, ' becomes...'
    insertion_sort(l2)
    print '... ', l2, ' after sorting'
    l3 = [1, 2, 3, 4]
    print l3, ' becomes...'
    insertion_sort(l3)
    print '... ', l3, ' after sorting'

output.txt

find_index() examples
---------------------
1 fits in [1, 3, 5, 7, 9] at index:  1
5 fits in [1, 3, 5, 7, 9] at index:  3
9 fits in [1, 3, 5, 7, 9] at index:  5
8 fits in [1, 3, 5, 7, 9] at index:  4

insertion_sort() examples
-------------------------
[1, 4, 2, 3]  becomes...
...  [1, 2, 3, 4]  after sorting
[4, 3, 2, 1]  becomes...
...  [1, 2, 3, 4]  after sorting
[1, 2, 3, 4]  becomes...
...  [1, 2, 3, 4]  after sorting