Option D: In the worst case, the number of comparisons for given Insertion Sort are $\frac{n(n-1)}{2}$.
Consider the set of numbers $1,2,3,4,5$. Some examples for which the number of comparisons are maximum are
- Descending order: $5,4,3,2,1$
- $3, 5, 4, 2, 1$
- $3,5,4,1,2$
There is more than $1$ sequence for which the number of comparisons is maximum.
$\therefore$ Correct answer: $D$
Let us see why other options are false.
Option A: Since option D is true, option A is false.
Option B: Given Insertion Sort makes $(n-1)$ comparisons when the input is already sorted in ascending order.
Hence option B is false.
Option C: Insertion Sort makes $\frac{n(n-1)}{2}$ comparisons only when the input is sorted in descending order.
Since the word only is used, this option is false.
Option E: Insertion Sort makes $\frac{n(n-1)}{2}$ comparisons whenever all the elements of $L$ are not distinct.
Not distinct means either all the elements are same or few elements are same and few are distinct.
When elements are same, number of comparisons are $n-1$.
When few elements are same and few are distinct, number of comparisons are always less than $\frac{n(n-1)}{2}$ because while comparing same elements we don’t enter while loop.
Hence option E is false.
Note: There can be more than $1$ sequence for maximum number of comparisons in insertion sort but maximum number of movements or swaps occur only when input is in Descending Order for this question.