Sorting algorithms - Data Structures and Problem Solving Using Java - page 356

the effect of the assignment statement is to swap the two items a[j] and
a[j-1] . (We avoid the actual excessive swapping by using the temporary vari-
able, but nonetheless it is an abstract swap.) Swapping two elements that are
out of place removes exactly one inversion, and a sorted array has no inver-
sions. Thus, if there are I inversions at the start of the algorithm, we must have
I implicit swaps. As O ( N ) other work is involved in the algorithm, the running
time of the insertion sort is O ( I + N ) , where I is the number of inversions in
the original array. Thus the insertion sort runs in linear time if the number of
inversions is O ( N ).
We can compute precise bounds on the average running time of the inser-
tion sort by computing the average number of inversions in an array. However,
defining average is difficult. We can assume that there are no duplicate ele-
ments (if we allow duplicates, it is not even clear what the average number of
duplicates is). We can also assume that the input is some arrangement of the
first N integers (as only relative ordering is important); these arrangements are
called permutations . We can further assume that all these permutations are
equally likely. Under these assumptions we can establish Theorem 8.1.

Theorem 8.1

The average number of inversions in an array of N distinct numbers is N N 1 ( - ) ⁄ 4 .

Proof

For any array of numbers, consider , which is the array in reverse order. For
example, the reverse of array 1, 5, 4, 2, 6, 3 is 3, 6, 2, 4, 5, 1. Consider any two num-
bers in the array, with . In exactly one of and , this ordered pair rep-
resents an inversion. The total number of these pairs in an array A and its reverse

A A r

( xy , ) yx > A r

A r

is NN 1 ( - ) ⁄ 2 . Thus an average array has half this amount, or NN 1 ( - ) ⁄ 4 inver-

sions.

Theorem 8.1 implies that insertion sort is quadratic on average. It also can be
used to provide a very strong lower bound about any algorithm that exchanges
adjacent elements only. This lower bound is expressed as Theorem 8.2.

Any algorithm that sorts by exchanging adjacent elements requires Ω N 2 () time on

Theorem 8.2

average.

Proof

The average number of inversions is initially NN 1 ( - ) ⁄ 4 . Each swap removes only

one inversion, so Ω N 2 () swaps are required.