#include <stdlib.h>
#include <stdio.h>

void bin_insertSort(int array[], int n)
{
    int i, j, temp, low, high, mid;
    for(i = 1; i < n; ++i)
    {
        temp = array[i];  //将当前需要被插入元素保存在temp中
        low = 0;
        high = i - 1;

        while(low <= high)   //利用折半查找确定被插入元素array[i]的合适位置
        {
            mid = (low + high) / 2;
            if(temp < array[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }

        for(j = i - 1; j >= low; --j)    //找到合适位置low, 将[low, i-1]中的元素依次后移一位
            array[j + 1] = array[j];

        array[low] = temp;    //插入元素array[i], 至此插入排序的一趟结束
    }
}

int main()
{
    int array[] = { 6, 3, 0, 6, 5, 8, 7, 4, 2, 7 };
    int n = sizeof(array) / sizeof(int);
    bin_insertSort(array, n);

    for(int i = 0; i < n; ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}