Insertion Sort

Insertion sort has a worst-case running time of Θ(n^2).

void insertionSort(int *a, int n)
{
    for (int j = 1; j < n; ++j)
    {
        int key = a[j];

        // Insert A[j] into the sorted sequence A[0, 1,...,j-1]
        int i = j-1;
        while ((i >= 0) && (key < a[i]))
        {
            a[i+1] = a[i];
            --i;
        }
        a[i+1] = key;
    }
}