P ython p rogramming e xercises

Solution Template 
Try to first write a solution from scratch. But if you have difficulty, you can use the following 
partial program as a starting place. Copy the following code from https://invpy.com/mergetwolists-
template.py and paste it into your code editor. Replace the underscores with code to make a working 
program: 
def mergeTwoLists(list1, list2): 
# Create an empty list to hold the final sorted results: 
result = ____ 
# Start i1 and i2 at index 0, the start of list1 and list2: 
i1 = ____ 
i2 = ____ 
# Keeping moving up i1 and i2 until one reaches the end of its list: 
while i1 < len(____) and ____ < len(list2): 
# Add the smaller of the two current items to the result: 
if list1[____] < list2[____]: 
# Add list1's current item to the result: 
result.append(____[i1]) 
# Increment i1: 
i1 += ____ 
else: 
# Add list2's current item to the result: 
result.append(____[i2]) 
# Increment i2: 
i2 += ____ 
# If i1 is not at the end of list1, add the remaining items from list1: 
if i1 < len(____): 
for j in range(i1, len(list1)): 
result.append(____[j]) 
# If i2 is not at the end of list2, add the remaining items from list2: 
if i2 < len(____): 
for j in range(i2, len(list2)): 
result.append(____[j]) 
# Return the merged, sorted list: 
return result 
The complete solution for this exercise is given in Appendix A and 
https://invpy.com/mergetwolists.py. You can view each step of this program as it runs under a debugger at 
https://invpy.com/mergetwolists-debug/. 

---

Python Programming Exercises, Gently Explained 
126 
Further Reading 
Merge sort uses this ―merge two sorted lists into a single sorted list‖ behavior as a step in its 
algorithm. You can learn more about merge sort and other recursive algorithms from my book, ―The 
Recursive Book of Recursion.‖ The full book is freely available under a Creative Commons license at 
https://inventwithpython.com/recursion/.

---

127