9.2 Insertion Sort

Here in the i^th iteration, the record a[i] is inserted into its proper position in the first i positions. $$\underbrace{a[1] \space \ldots \space a[i-1]}_{\begin{array}{l}\mbox{sorted (may not be as}\\\mbox{in the final order)}\end{array}}^{}\,$$$$\underbrace{a[i] \space \ldots \space a[n]}_{\begin{array}{l}\sp......{Insert $a[i]$ into an} \\\space \ \mbox{appropriate place}\end{array}}^{}\,$$ Let us assume, for the sake of convenience, a fictitious record a[0] with key value = - $\infty$.

    {

            for(i = 2;i < = n;i + +)

            {

                j = i ;

                while (key of a[j] < key of a[j - 1])

                {

                    swap records a[j] and a[j - 1];

                    j = j - 1

                }

            }

    }

• Exhibits the worst case performance when the initial array is sorted in reverse order.
• Worst case and average case performance is O(n²)