Insertion Sort

An insertion sort is one that sorts a set of records by inserting records into an existing sorted file.

Below is the insertion sort procedure code

void InsertionSort(int x[],int n)
{
    int i,k,y;
    for(k=1;k<n;k++)
    {
        y=x[k];
        for(i=k-1;i>=0 && y<x[i];i--)
            x[i+1] = x[i];
        x[i+1]=y;
    }
}

Time complexity iss O(n2) if the file is initially sorted in reverse order. On average case also its time complexity is O(n2).