Insertion sort

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

void insertionSort(int arr[], int  n)
{
    int i, key, j;
    for (i = 1; i < n; ++i)
    {
        key = arr[i];
        j = i - 1;

        //move elements between arr[0.. i-1] one position
        //ahead of theie current position, whhich are greater then key
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;

    }
}