Insertion sort has time complexities :

• Worst-case performance: О(n^2) comparisons and swaps
• Best-case performance: O(n) comparisons, O(1) swaps
• Average performance: О(n^2) comparisons and swaps

• In the best case elements are already sorted.

BINARY SEARCH INSERTION SORT

• To find the position of an element to be inserted into the sorted part of the array, we can use binary search which reduces the time complexity of comparison of a worst-case scenario to O(N log N)

• The algorithm as a whole still has a running time of O(n^2) on average because of the series of swaps required for each insertion.

• But this increases the number of comparisons in the Best Case scenario, to handle this we can just check if the element is greater than the previous element before calling the binary search function. This is the tweak to reduce comparison in the best-case scenario.

• Example, if the array is [2,3,4,5,1], we need not call the binary search function for each element , we need to call it only for '1'. So we start iterating from index 1 and check :

if (Array[i]<Array[i-1])

• If true we call perform Binary Insertion sort, else we can infer that the element is in the right position and go to the next element

• In this way, we are saving a lot of comparisons by not calling the Binary search function on every element.

• Binary Insertion sort is efficient when the array size is small

The function below will return the index where the element is to be inserted

def binarySearch(Array, size, key,totalComparison):
    start = 0
    end = size
    while(start < end):
        totalComparison+=1;
        middle = (start + end)//2
        if (Array[middle] <= key):
            start = middle + 1
        else:
            end = middle
    return start,totalComparison

def binaryInsertionSort(Array,totalSwaps,totalComparison):
    for i in range (1,len(Array)):
        if(Array[i]<Array[i-1]):
            swaps=0
            key = Array[i]
            pos,totalComparison = binarySearch(Array, i, key,totalComparison)
            # 'pos' will now contain the index where 'key' should be inserted.
            j = i
            # Shifting every element from 'pos' to 'i' towards right.
            swaps = i-pos #Keeps count of swaps at current Iteration 
            totalSwaps+=i-pos; #Keeps count of total swaps
            while(j > pos):
                Array[j] = Array[j-1]
                j = j-1
            # Inserting 'key' in its correct position.
            Array[pos] = key
            print("Iteration :",i,",BinarySearch function called on element at index",i,",swaps made at this iteration =",swaps,",Array=", *Array)
        else:
            totalComparison+=1;
            print("1 comparison and 0 swaps at iteration",i," (BinarySearch function not called on element at index",i,"), Array =", *Array)

    return totalSwaps,totalComparison

Array = [5, 4, 3, 2, 1]
totalSwaps=0;totalComparison=0;
print("Given array :",*Array)
totalSwaps,totalComparison=binaryInsertionSort(Array,totalSwaps,totalComparison)
print("\n\nTotal swaps for sorting the Array = ",totalSwaps)
print("Total comparisons for sorting the Array = ",totalComparison)

OUTPUTS

BEST CASE (ARRAY IS ALREADY SORTED)

AVERAGE CASES

WORST CASE