Python-сообщество

 def binarySearch(aList, start, end, value): 
#Return the position where value is or should be inserted.
    while start <= end: 
        mid = (start + end) // 2 
        if aList == value: 
            return mid 
        if value < aList: 
            end = mid - 1 
        else: 
            start = mid + 1 
    return start
def insertionSort(aList):
#Sort aList in ascending order. 
    for index in range(1, len(aList)):
        key = aList
        pos = index
        while pos > 0 and aList > key:
            aList = aList
            pos = pos - 1
        aList = key

 def insertion_sort(a_list):
    for index in range(1, len(a_list)):
        value = a_list[index]
        pos = binary_search(a_list, value, 0, index-1)
        a_list = a_list[:pos] + [value] + a_list[pos:index] + a_list[index+1:]
    return a_list
items = [4,3,2,1]
print ('expected ',[1, 2, 3, 4])
insertion_sort(items)
print('got ',items)