Search code examples
algorithminversion

Inversion for insertion sort!

This a question I found in the Wikipedia site (I want to learn sort algorithms very well). Anyway, this is a question - could you explain to me how I can show it?

Exercise: Show that Algorithm Insertion Sort (A) runs in time O(n + I) given that I is the number of inversions in the array A.

Solution

  • Look at the Implementation and Analysis sections of this page.

    Consider the algorithm presented there:

    private static void insertionsort()
{
    int i, j, t;
    for (i=1; i<n; i++)
    {
        j=i;
        t=a[j];
        while (j>0 && a[j-1]>t)
        {
            a[j]=a[j-1];
            j--;
        }
        a[j]=t;
    }
}

    Notice that the while loop runs for v[i] iterations, where v[i] is the number of inversions caused by element i. This should make the proof there very easy to understand.