Binary insertion sort uses binary search to find an appropri

Binary insertion sort uses binary search to find an appropriate position to insert A[i] among the previously sorted A[0] ... A[i1]. Give the Pseudocode for binary insertion sort AND determine this algorithim\'s worst-case effiency regarding the key comparisons.

Solution

Determine this algorithim\'s worst-case effiency regarding the key comparisons:

If array to be sorted is in reverse order then it is the worst case effiency. Reverse order means each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n²)).