Question: How many comparisons does the insertion sort use to sort the list n, n - 1,..., 2, 1? The binary insertion sort is a variation of the insertion sort that uses a binary search technique (see Exercise) rather than a linear search technique to insert the ith element in the correct place among the previously sorted elements.
Exercise: Describe an algorithm based on the binary search for determining the correct position in which to insert a new element in an already sorted list.