#include
using namespace std;
int binarysearch(int L,int R,int a[],int x,int i)
{
int mid = (L + R) / 2;
if (i == 1 && x > a[mid])
{
return R;
}
if (a[i] > a[i - 1])
{
return i;
}
if (L > R)
{
return 0;
}
if (x < a[0])
{
return 0;
}
if (a[mid] > x&& a[mid - 1] < x)
{
return mid;
}
else if (a[mid] < x)
{
return binarysearch(mid + 1, R, a, x,i);
}
else
return binarysearch(L, mid - 1, a, x,i);
}
void chen(int a[], int k, int i)
{
int temp = a[i];
for (int j = i; j > k; j--)
{
a[j] = a[j-1];
}
a[k] = temp;
}
void insertionSort(int a[],int n)
{
for (int i = 1; i < n; i++)
{
int k = binarysearch(0, i, a, a[i],i);
chen(a, k, i);
}

}
void main()
{
int a[] = { 1213,1324,3434,254,4335,64575,234,12,532 };
int n = 9;
insertionSort(a, n);
for (int i = 0; i < n; i++)
{
cout << a[i] << endl;
}

}