{}
#include <stdio.h>
// A binary search based function to find 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;
int selected;
for (i = 1; i < n; ++i)
{
j = i;// - 1;
selected = a[i];
// find location where selected should be inserted,
loc = binarySearch(a, selected, 0, i-1);
// Move all elements after location to create space
while (j > loc)
{
a[j] = a[j-1];
j--;
}
a[j] = selected;
}
}
// Driver Code
int main()
{
int a[] = {3,2,4,10, 5}; //{2,4,8,10,12,11};
int n = sizeof(a)/sizeof(a[0]);
int i;
insertionSort(a, n);
printf("\n\nSorted array: \n");
for (i = 0; i < n; i++) printf("a[%d]:%d ", i, a[i]);
return 0;
}