70 SORTING ALGORITHMS
have. If our first sublist has the elements in locations 1 and 1 + increment,
the last sublist has to start in location increment. The last time the while
loop is executed, passes will have a value of 1, which will make increment 1
for the last InsertionSort.
The analysis of this algorithm depends on the analysis that we did of
InsertionSort. Before we begin the analysis of Shellsort, recall that in
Section 3.1, we saw that for a list with N elements the worst case for insertion
sort was and the average case for insertion sort was.■ 3.3.1 Algorithm Analysis
In this analysis, we will first determine the number of times we call the
InsertionSort function and the number of elements in the lists for those
calls. Let’s look at the specific case when the list size is 15. On the first pass,
increment is 7 and so we make seven calls with lists of size 2. On the second
pass, increment is 3, and so we make three calls with lists of size 5. On the
third pass and last pass, increment is 1, and so we make one call with a list of
size 15. From the above formulas, we see that for a list of size 2, Insertion-
Sort will do one comparison in the worst case. For a list of size 5, it will do
10 comparisons in the worst case. For a list of size 15, it will do 105 compari-
sons in the worst case. If we add all of this up together, we find that we get a
total of 142 comparisons (7 * 1 + 3 * 10 + 1 * 105). But is this a good esti-
mate?
If you look back at the analysis of Section 3.1.1, you will see that we said
the worst case for insertion sort occurs when each element to be added has to
be put at the front of the list. On the last pass of our Shellsort algorithm,
we know that this worst case cannot possibly occur because of the sorting that
occurred in the earlier passes. Maybe a different approach will help us figure
out how much work is left.
When analyzing sorting algorithms, we will sometimes consider the number
of inversions in a list. An inversion is a pair of elements in the list that are out of
order. For example, the list [3, 2, 4, 1] has four inversions, namely, (3, 2), (3,
1), (2, 1), and (4, 1). You should see that a list in reverse order has the worst
number of inversions possible:.
One way to look at the work a sorting algorithm does is to count the num-
ber inversions between the current permutation of the elements and a sorted()N^2 – N ⁄ 2 N^2 ⁄ 4()N^2 – N ⁄ 2