We also note that each element to be sorted must be compared one or
many times with the elements already sorted. In the best case, the elements will be sorted already, and each element
will require only a single comparison, so the best-case performance of the insertion sort is ??(n).
In the worst case, the elements to be sorted will be in reverse order, so that every element will require comparison
with every element already sorted. The second number will be compared with the first, the third with the second
and first, the fourth with the third, second, and first, etc. If there were four numbers in reverse order, the number of
comparisons would be six. In general, the number of comparisons in the worst case for the insertion sort will be:
n2/2 - n/2
The number of comparisons will grow as the square of the number of elements to be sorted. The negative
term of -n/2, and the division of n2 by the constant 2, mean that the rate of growth in number of comparisons
will not be the full rate that n2 would imply. However, for very large values of n, those terms other than
18 ALGORITHMS [CHAP. 2
n2 become relatively insignificant. Imagine the worst case of sorting a million numbers. The n2 term will
overwhelm the other terms of the equation.
Pages:
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59