@@ -0,0 +1,1486 @@
+#Binary Insertion Sort using python%0A%0A#using binary search to look for location to insert current value%0A#low is set as the lowest value in array and high is the highest value%0A#in sorted array%0Adef BS(arr, val, low, high):%0A%0A    #return the location of the smallest sorted value%0A    #that is greater than the current value to be inserted%0A    if low == high:%0A        if arr%5Blow%5D %3E val:%0A            return low%0A        else:%0A            return low + 1%0A%0A    if low %3E high:%0A        return low%0A%0A    mid = (low + high) / 2%0A%0A    #run binary search in the second half of sorted array%0A    #when the value to be inserted is greater than the average%0A    #of highest and lowest value in sorted array%0A    if arr%5Bmid%5D %3C val:%0A        return BS(arr, val, mid+1, high)%0A%0A    #run binary search in the first half of sorted array%0A    #when the value to be inserted is smaller than the average%0A    #of highest and lowest value in sorted array%0A    elif arr%5Bmid%5D %3E val:%0A        return BS(arr, val, low, mid-1)%0A%0A    #return the location of the center when the value to be inserted%0A    #and the average of highest and lowest value in sorted array%0A    #is equal%0A    else:%0A        return mid%0A%0Adef BIS(arr):%0A    #run binary search in every element in array%0A    #and immediately sort the array%0A    for i in xrange(1, len(arr)):%0A        val = arr%5Bi%5D%0A        j = BS(arr, val, 0, i-1)%0A        arr = arr%5B:j%5D + %5Bval%5D + arr%5Bj:i%5D + arr%5Bi+1:%5D%0A    return arr%0A%0Aprint (%22Sorted array: %22)%0Aprint BIS(%5B37, 23, 0, 17, 45, 9, 80, 9, 9%5D)%0A

add binary insertion sort in python