(a) Explain the Insertion Sort Algorithm for ordering a list L of n objects.

Calculate how many comparisons are needed in an insertion sort of the list [23, -4, 8, 1, -20, 5].

(b) Prove that the worst case complexity of Insertion Sort is O (n^2) .

Exactly how many comparisons are made, in the worst case, in an insertion sort of n objects?

(c) If an Insertion Sort of 10^4 items took 70 seconds, how long would you expect it to take for an insertion sort of

i. 10^6 items?

ii. 1, 000 items