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] +
" "
);
}
}