Optimized Insertion Sort

Insertion Sort can be helpful when you only want to place a single element in the array.
However, it is not efficient if there data set is large because of it's number of comparisons and shifts.
I found that we can actually do small modification in the Insertion sort and can reduce number of comparisons.

While working on the Binary Search we can modify the binary search in such way that if element is not present in array it will return the -(index-1); this will denote element's index if you want to insert this into array.
In java I found that they have already done this kind of implementation however, people who work in other languages can write their own implementation
like below in C:

int bsearch(int low, int high, int item)
{
     int  mid;
    int midItem;
     while(low <= high)
     {
        mid = (low+high)/2;
        midValue=arr[mid];
        if(item == midItem) return mid;
        if(item < midItem)
           high = mid - 1;
        else
           low = mid + 1;
    }
    return -low-1;
}

• So instead of comparing each element to other sorted elements, we can simply perform the binary search on the sorted part of array and can find the location where new element should be inserted. In this way we can save the time of comparison, Yes shift will still require. 
• However, in java there is API System.arraycopy which can help you in copying the entire array at one shot, yes it is better than a loop to shift each element.
• I tried this on more than one dimensional array and didn't get the desired results.