86 SORTING ALGORITHMS
NA is the number of elements in list A. Notice that if all of the elements of list
B are smaller than the first element of A, the resulting number of comparisons
would be NB, where NB is the number of elements in list B.
What if the first element of A is greater than the first element of B but all of
the elements of A are smaller than the second element of B? We would com-
pare A[1] and B[1] and move B[1] to C. We now find ourselves in the same
position we were in the last case, where we will compare every element of A
with B[2] as they are moved to the result. This time, however, we not only
have done NA comparisons of the elements of A with B[2], but we also did a
comparison of A[1] and B[1], so the total number of comparisons in this case is
NA + 1. If we consider other arrangements, we start to see that the case pre-
sented in the first paragraph of this subsection might be the best case, and it is.
We saw that if all the elements of list A were between B[1] and B[2], we did
more comparisons than if all of the elements of A were smaller than all of the
elements of B. Let’s see if taking this to the extreme gives the worst case. Con-
sider what happens if the elements of A and B are “interleaved” based on their
value. In other words, what happens if the value of A[1] is between B[1] and
B[2], the value of A[2] is between B[2] and B[3], the value of A[3] is between
B[3] and B[4], and so on. Notice that each comparison moves one element
from either A or B into list C. Based on the example ordering above, we move
an element of B, then one of A, then one of B, then one of A, until we have
moved all but the last element of A. Because the comparisons resulted in mov-
ing all but the last element of A, we will have done NA + NB 1 comparisons
in this worst case.■ 3.6.2 MergeSort Analysis
Now that we know the range of complexity of MergeLists, we can now
look at MergeSort. Based on the techniques of Section 1.5, we look at the
parts of the MergeSort algorithm. First, we notice that the function is called
recursively as long as first is less than last. This means that if they are equal
or if first is greater than last, there is no recursive call. If first is equal to
last, this represents a list of size 1. If first is greater than last, this repre-
sents a list of size 0. In both of these cases, the algorithm does nothing, so the
direct solution has zero comparisons.
The division of the list into two parts is done by the calculation of middle.
We see this calculation is done without any comparisons, so the division step is