Question

Give a worst-case input sequence of 6 numbers for Insertion Sort, containing the numbers

21, 16, 77, 3, 8, and 11.No explanation/proof required.

Answer 1

The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n²)).

So the worst case input sequence would be :

(77, 21, 16, 11, 8, 3)