// C program for implementation of binary insertion sort
#include <stdio.h>
 
// A binary search based function to find the position
// where item should be inserted in a[low..high]
int binarySearch(int a[], int item, int low, int high)
{
    if (high <= low)
        return (item > a[low])?  (low + 1): low;
 
    int mid = (low + high)/2;
 
    if(item == a[mid])
        return mid+1;
 
    if(item > a[mid])
        return binarySearch(a, item, mid+1, high);
    return binarySearch(a, item, low, mid-1);
}
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
    int i, loc, j, k, selected;
 
    for (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected sould be inseretd
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = selected;
    }
}
 
// Driver program to test above function
int main()
{
    int a[] = {37, 23, 0, 17, 12, 72, 31,
              46, 100, 88, 54};
    int n = sizeof(a)/sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
        printf("%d ",a[i]);
 
    return 0;
}

package com.codingeek.algorithms.sorting;
 
import java.util.Arrays;
 
class BinaryInsertionSort{
 
    public static void main(String[] args) {
        final int[] input = { 4, 10, 3, 1, 9, 15 };
        System.out.println("Before Sorting - " + Arrays.toString(input));
        new BinaryInsertionSort().sort(input);
        System.out.println("After Sorting - " + Arrays.toString(input));
    }
     
    public void sort(int array[]) {
        for (int i = 1; i < array.length; i++) {
               int x = array[i];
                
               // Find location to insert using binary search
               int j = Math.abs(Arrays.binarySearch(array, 0, i, x) + 1);
                
               //Shifting array to one location right
               System.arraycopy(array, j, array, j+1, i-j);
                
               //Placing element at its correct location
               array[j] = x;
        }
}