using System;
class GFG {
static int binarySearch(int []a, int item, int low, int high)
{
while (low <= high) {
int mid = low + (high - low) / 2;
if (item == a[mid])
return mid + 1;
else if (item > a[mid])
low = mid + 1;
else
high = mid - 1;
}
return low;
}
static void insertionSort(int []a, int n)
{
int i, loc, j, selected;
for (i = 1; i < n; ++i) {
j = i - 1;
selected = a[i];
loc = binarySearch(a, selected, 0, j);
while (j >= loc) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = selected;
}
}
public static void Main (String[] args)
{
int []a = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
int n = a.Length, i;
insertionSort(a, n);
Console.WriteLine("Sorted array:");
for (i = 0; i < n; i++)
Console.Write(a[i] +" ");
}
}
