How does Binary Insertion Sort Work?

Question

I know how binary search works, and also know how Insertion sort works but this code is about Binary Insertion Sort and i have problem in understanding how it works.

static void Main(string[] args)
{
    int[] b = BinarySort(new[] { 4, 3, 7, 1, 9, 6, 2 });
    foreach (var i in b)
        Console.WriteLine(i);
}
public static int[] BinarySort(int[] list)
{
    for (int i = 1; i < list.Length; i++)
    {
        int low = 0;
        int high = i - 1;
        int temp = list[i];
        //Find
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (temp < list[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        //backward shift
        for (int j = i - 1; j >= low; j--)
            list[j + 1] = list[j];
        list[low] = temp;
    }
    return list;
}

I don't understand what this part do:

//backward shift
for (int j = i - 1; j >= low; j--)
    list[j + 1] = list[j];
list[low] = temp;

and what is the purpose of using binary search here? Can you tell me how binary insertion sort works? (c# console)

code source:http://w3mentor.com/learn/asp-dot-net-c-sharp/asp-dot-net-language-basics/binary-insertion-sort-in-c-net/

Answer 1

Binary insertion sort works as insertion sort, but it separates locating the insertion point from the actual insertion.

Insertion sort implemented for an array will move items at the same time as locating the insertion point. While looping through the items to find the insertion point, it will also shift the items to make room for the insertion.

Binary insertion sort will make use of the fact that the items that are already sorted are sorted, so it can use a binary search to find the insertion point. As the binary search can't also shift the items to make room for the insertion, that has to be done in a separate step after the insertion point has been found.

The code that you wanted explained is the code that shifts the items to make room for the insertion.