Question :
Suppose the array begins with 0, followed by the remaining even integers in descending order, followed by the odd numbers in descending order.
(For n = 8, the array would be [0,8,6,4,2,7,5,3,1].)
How many comparisons will insertion sort perform when it is executing the pass that moves the element at index n-1 into position?
(Do not assume n = 8.)