Insertion Sort

O(n) – O(n2)
void InsertionSort(int arr[],int n)
{
int idx,tmp;
for(int i=1;i<n;i++)
{
idx = i;
tmp = arr[i];
while(idx>0 && comparer(arr[idx-1],tmp))
{
arr[idx] = arr[idx-1];
idx–;
}
arr[idx]=tmp;
}
}