// C++
void binaryInsertionSort(int array[], int length) {
    for (int i = 1; i < length; ++i) {  // 遍历无序序列
        int left = 0;  // 有序序列左指针
        int right = i - 1;  // 有序序列右指针
        int key = array[i];  // 记录准备插入的元素
        while (left <= right) {  // 二分查找
            int mid = (left + right) / 2;  // 有序序列中间位置
            if (array[mid] < key) {
                left = mid + 1;
            } else if (array[mid] > key){
                right = mid - 1;
            } else {
              left = mid;
              break;
    }
        }
        // 找到元素插入位置后，整体后移
        for (int j = i - 1; j >= left; --j) {
            array[j + 1]  = array[j];
        }
        array[left] = key;  // 填入对应位置
    }
}