CASE STUDY
564
pretend that the names are on index cards in two stacks rather than in two lists. If we
pick up the first card in each stack and compare them, three possibilities arise:1.The name on the first stack comes alphabetically before the name on the
second stack.
2.The name on the second stack comes alphabetically before the name on the
first stack.
3.The names are the same.
If the name on the first stack comes first, we would put the card in the output stack
face down. If the name on the second stack comes first, we would put that card in the
output stack face down. If the names are the same, we would put one of the cards on
the output stack face down and tear up the other card. The stack from which the card
was removed now has a new card on the top (or both stacks have new cards on top),
and we repeat the comparing process. This algorithm allows us to look at only one
name from each list at a time, so we do not search the second list.
“Picking up the first card in each stack” is equivalent to examining the name from the
first entry in each list. “Compare them” is a call to theNameclass methodcompareTo. Recall
thatcompareToreturns a negative value if the object comes before the parameter, zero if
the two are the same, and a positive value if the parameter comes before the object.
“Put a card on the output stack face down” translates into inserting the entry into
the combined list. “Tear up” translates into not processing the entry. “New card” trans-
lates into getting the next entry.
What halts the processing? In our by-hand algorithm, we stopped comparing names
when one or both of the stacks became empty. A stack is “empty” when one or both
lists run out of entries. Because we know how many items are in each list, we can count
how many times we get a new item from each list and stop when we have accessed the
last one in one of the lists. One list may run out of entries before the other, in which
case those remaining entries must be inserted into the result.Merge
Set up for processing firstList
Set up for processing secondList
whilemoreData1 AND moreData2
Set compareResult to 'firstEntry comes before secondEntry'
ifcompareResult < 0
Put firstEntry in resultList
else ifcompareResult > 0
Put secondEntry in resultList
else
Process both entries
ifmoreData1
Insert rest of firstList into resultList
else ifmoreData2
Insert rest of secondList into resultList