How can I change the usual insertion sort so that the algorithm uses a binary search?

Question

Programming

The usual insertion algorithm:

for(int i=1;i<n;i++)
{
    temp=array[i];
    index=i;
    while(index>0 && array[index-1]>=temp)
    {
        array[index]=array[index-1];
        index--;
    }
    array[index]=array[i];
}

Answer 1

It is useless to fasten binary search to sorting by inserts. In addition to finding the place where a new element is inserted, this element must also be inserted. With this array, you will have to shift O(n) elements with each insertion. In a linked list, you wouldn't have to shift the elements, but it's impossible to do a binary search there, because there's no fast random search.
The implementation you provided is pretty fast. Here the search for the insertion point and the shifts of all elements are combined. Theoretically, you can first do a binary search and use, say, a for loop with a fixed number of iterations instead of a while loop. This will reduce the number of comparisons in the loop by 2 times, but will add some comparisons and non-local memory accesses in bin.search. It will probably work faster only if the input data is given almost in reverse order. On average, it will work worse.
A much better implementation would be to initially reserve the first element in the array and put a very small number there. And write the data after it. Then in the while loop it will not be necessary to compare index>0. This implementation will be much faster than the additional binary search.