Binary Insertion Sort Implementation Python

Question

While studying algorithms, I found an algorithm, which is basically an Insertion Sort but it uses Binary Search instead of WHILE-loop statement in shifting elements backward.

I wrote the following implementation code and it works fine with given inputs.

My question is 1) Are there any improvements to my code? 2) I still cannot understand why it has quadratic time despite using binary search. I think I need help in understanding this.

Thank you for your valued advice in advance :)

A=[3,25,18,41,52,26,38,57,9,49]
def InsertionSort_improved(A):
    for k in range(1,len(A)):
        key = A[k]
        low = 0
        high = k-1
        BinarySearch(A,low,high,key,k)

def BinarySearch(A,low,high,key,k):
    if low<high:
        mid= (low+high)//2
        if A[mid] == key:
            for i in range(k,mid,-1):
                A[i] = A[i-1]
            A[i-1] = key
        elif A[mid] < key:
            BinarySearch(A, mid+1, high, key, k)
        else:
            BinarySearch(A, low, mid, key, k)
    else:
        mid=(low+high)//2
        if A[mid]>key:
            for j in range(k,mid,-1):
                A[j] = A[j-1]
            A[j-1] = key

InsertionSort_improved(A)
print(A)

Answer 1

Long story short: because of these two lines.

for j in range(k,mid,-1):
    A[j] = A[j-1]

Insertion of an element goes like this:

• find where to insert the new element;
• shift a lot of elements to make room for the new element.

The code you've found uses binary search to speed up the first step, which becomes O(log(n)) instead of O(n).

But then it still needs to shift the elements, and this is done with a simple for-loop, which takes O(n) time.

Note that when doing insertion sort on a linked list instead of an array, shifting is no longer necessary, so the second step becomes O(1)... But with a linked list, binary search is not possible, so the first step remains O(n).

Conclusion: on arrays as well as on linked lists, insertion sorts remains a quadratic algorithm.