Apply insertion sort to sort the list W, E, L, C, O, M, E in alphabetical order.

Let A[0..n 1] be an array of n sortable elements. (For simplicity, you may assume that all the elements are distinct.) A pair (A[i], A[j ]) is called an inversion if i A[j ].

a. What arrays of size n have the largest number of inversions and what is this number? Answer the same questions for the smallest number of inversions.

b. Show that the average-case number of key comparisons in insertion sort is given by the formula