Binary Insertion Sort

// O(nlogn) – O(n2)
void BinInsSort(int m[],int n)
{
int i,left,right,tmp,mid;
for(i=1;i<n;++i)
{
left = 0;
right = i;
tmp = m[i];
while(left<right)
{
mid = (left+right)/2;
if(m[mid]<tmp) left=mid+1;
else right = mid;
}
for(int j=i;j>left;–j)
swap(m[j],m[j-1]);
}

}