123
E X E R C I S E # 4 0 : M E R G I N G T W O S O R T E D
L I S T S
mergeTwoLists([1, 3, 6], [5, 7, 8, 9])
→
[1, 3, 5, 6, 7, 8, 9]
One of the most efficient sorting algorithms is the merge sort algorithm.
Merge sort has two
phases: the dividing phase and the merge phase. We won’t dive into this advanced algorithm in this
book. However, we can write code for the second half: merging two pre-sorted lists of integers into a
single sorted list.
Exercise Description
Write a mergeTwoLists() function with two parameters list1 and list2.
The lists of
numbers passed for these parameters are already in sorted order from smallest to largest number. The
function returns a single sorted list of all numbers from these two lists.
You could write this function in one line of code by using Python’s sorted() function:
return sorted(list1 + list2)
But this would defeat the purpose of the exercise, so don’t use the sorted() function or
sort()
method as part of your solution.
These Python assert statements stop the program if their condition is False.
Copy them to
the bottom of your solution program. Your solution is correct if the following assert statements’
conditions are all True:
assert mergeTwoLists([1, 3, 6], [5, 7, 8, 9]) == [1, 3, 5, 6, 7, 8, 9]
assert mergeTwoLists([1, 2, 3], [4, 5]) == [1, 2, 3, 4, 5]
assert mergeTwoLists([4, 5], [1, 2, 3]) == [1, 2, 3, 4, 5]
assert mergeTwoLists([2, 2, 2], [2, 2, 2]) == [2, 2, 2, 2, 2, 2]
assert mergeTwoLists([1, 2, 3], []) == [1, 2, 3]
assert mergeTwoLists([], [1, 2, 3]) == [1, 2, 3]
Try to write a solution based on the information in this description. If you still have trouble
solving
this exercise, read the
Solution Design and Special Cases and Gotchas sections for
additional hints.
Prerequisite concepts: lists, while loops,
Boolean operators, append(), for loops, range()
with two arguments, len()
