P ython p rogramming e xercises

Solution Design 
The lists of integers, already in sorted order, are passed to the function as parameters list1 and 
list2
. The algorithm begins with two variables, i1 and i2, which both begin at index 0 of their 
respective lists. We also create a blank list in a variable named result which stores the merged 
results of the two lists. 
Inside of a while loop, the code does the following: 

Look at the numbers that i1 and i2 point to. 

Append the smaller of the two numbers to result. 

If i1’s number was appended, increment i1 to point to the next number in list1. 
Otherwise, increment i2 to point to the next number in list2. 

Repeat until either i1 or i2 has gone past the end of their list.
For example, Figure 40-1 shows the first three iterations of the loop when merging lists [1, 3, 
6]
and [5, 7, 8, 9]. 
Figure 40-1: The first three iterations of the loop that merges two lists. 
Think of this code as like an asymmetrical zipper: the i1 and i2 variables keep moving right 
along their respective lists, appending their values to result. When either i1 or i2 reaches the end of 
their list, the rest of the other list is appended to result. This result list contains all of the 
numbers in list1 and list2 in sorted order, so the function returns it. 

---

Python Programming Exercises, Gently Explained 
125 
Special Cases and Gotchas 
Keep in mind that while the list1 and list2 parameters must be sorted lists, they aren’t 
required to be the same length. 
If either of these list arguments to mergeTwoLists() isn’t sorted, the function will return a 
merged list that is also not in sorted order. For this exercise, however, we’ll assume that 
mergeTwoLists()
is always called with valid arguments. 
Now try to write a solution based on the information in the previous sections. If you still have 
trouble solving this exercise, read the Solution Template section for additional hints.