Analysis of Algorithms : An Active Learning Approach

3.6 MERGE SORT 85

finalEnd = end2
indexC = 1
while (start1 ≤ end1) and (start2 ≤ end2) do
if list[start1] < list[start2] then
result[indexC] = list[start1]
start1 = start1 + 1
else
result[indexC] = list[start2]
start2 = start2 + 1
end if
indexC = indexC + 1
end while

// move the part of the list that is left over
if (start1 ≤ end1) then
for i = start1 to end1 do
result[indexC] = list[i]
indexC = indexC + 1
end for
else
for i = start2 to end2 do
result[indexC] = list[i]
indexC = indexC + 1
end for
end if

// now put the result back into the list
indexC = 1
for i = finalStart to finalEnd do
list[i] = result[indexC]
indexC = indexC + 1
end for

■ 3.6.1 MergeLists Analysis
Because all of the element comparisons occur in MergeLists, we begin ana-
lyzing there. Let’s look at the case where all of the elements of list A are smaller
than the first element of list B. What will happen in MergeLists? We will
begin by comparing A[1] and B[1] and because A[1] is smaller we will move it
to C. We then compare A[2] with B[1] and move A[2] because it is smaller.
This process will continue comparing each element of A with B[1], because
they are all smaller. This means that the algorithm does NA comparisons, where