Merge two sorted lists in Python

Question

Merge two sorted lists

# Input: lst1 {List}
# Input: lst2 {List}
# Output: {List}
#
# Example: merge([1, 4, 7], [2, 3, 6, 9]) => [1, 2, 3, 4, 6, 7, 9]
#
def merge(items1, items2):
 # merge 2 list
 # divide and conquer
 # combine - step2
 ("\n"
 " while left_index is not the length of left_array and right_index is not the length of right_array\n"
 " if left_array[left_index] < right_array[right_index]\n"
 " add left_array[left_index] to merged array\n"
 " left_index + 1\n"
 " else\n"
 " add right_array[right_index] to merged_array\n"
 " right_index + 1 ")
 # if we've passed the end of either list, then extend the sorted list
 # with what remains in the other
 left_pointer = 0
 right_pointer = 0
 sorted_list = []
 while len(sorted_list) < len(items1) + len(items2):
 left_item = items1[left_pointer]
 right_item = items2[right_pointer]
 if left_item < right_item:
 sorted_list.append(left_item)
 left_pointer += 1
 else:
 sorted_list.append(right_item)
 right_pointer += 1
 if right_pointer >= len(items2):
 sorted_list.extend(items1[left_pointer:])
 break
 if left_pointer >= len(items1):
 sorted_list.extend(items2[right_pointer:])
 break
 return sorted_list

test cases that i am working on

print('merge tests')
test_count = [0, 0]
def test():
 results = merge([1, 4, 7], [2, 3, 6, 9])
 return (len(results) == 7 and
 results[0] == 1 and
 results[1] == 2 and
 results[2] == 3 and
 results[3] == 4 and
 results[4] == 6 and
 results[5] == 7 and
 results[6] == 9)
expect(test_count, 'should return [1, 2, 3, 4, 6, 7, 9] when merging [1, 4, 7]', test)
def test():
 results = merge([], [2, 3, 6, 9])
 return (len(results) == 4 and
 results[0] == 2 and
 results[1] == 3 and
 results[2] == 6 and
 results[3] == 9)
expect(test_count, 'should handle inputs when left argument is empty array', test)
def test():
 results = merge([1, 4, 7], [])
 return (len(results) == 3 and
 results[0] == 1 and
 results[1] == 4 and
 results[2] == 7)
expect(test_count, 'should handle inputs when right argument is empty array', test)
def test():
 results = merge([], [])
 return len(results) == 0
expect(test_count, 'should handle two empty arrays as inputs', test)
print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')
class TestObject(object):
 def __init__(self, x, y):
 self.x = x
 self.y = y
 def __lt__(self, other):
 return self.x < other.x
 def __str__(self):
 return "LTO (%d, %d)" % (self.x, self.y)

• Josiah: In the tests, I can't see any reason to avoid simple list equality: e.g. results == [1,2,3,4,6,7,9]

Answer 1

Bug

• Your code does not work when either the left or right array is empty.

left_item = items1[left_pointer]
right_item = items2[right_pointer]

When item1 or item2 is an empty array this will break with an IndexError.

if right_pointer >= len(items2):
 sorted_list.extend(items1[left_pointer:])
 break
if left_pointer >= len(items1):
 sorted_list.extend(items2[right_pointer:])
 break

You should move this piece of code up to avoid the issue. Now it will break when either is empty.

Tests

• I think you can improve your tests quite some bit using the builtin unittest framework.

---

import unittest
class TestMergeSort(unittest.TestCase):
 def test_normal_merge(self):
 left = [1, 4, 7]
 right = [2, 3, 6, 9]
 out = [1, 2, 3, 4, 6, 7, 9]
 self.assertEqual(merge(left, right), out)
 def test_right_empty(self):
 left = [1, 4, 7]
 right = []
 out = [1, 4, 7]
 self.assertEqual(merge(left, right), out)
 def test_left_empty(self):
 left = []
 right = [2, 3, 6, 9]
 out = [2, 3, 6, 9]
 self.assertEqual(merge(left, right), out)
if __name__ == "__main__":
 unittest.main()

Merge function

• An easier way would be to pop the left sides (index=0) of the list and append to the result until either one is empty, after that you can add the remaining to the result.
• Naming: I believe you should rename your item1 and item2 to left and right for clarity.
• This will no longer have the bug, that it will raise an IndexError when either of the list's are empty.

---

def merge_sorted_lists(left, right):
 result = []
 while left and right:
 if left[0] < right[0]:
 result.append(left.pop(0))
 else:
 result.append(right.pop(0))
 return result + left + right

• NinjaG: I'm glad that you are able to point out the edge cases that I need to handle. Good tests.

Answer 2

One obvious improvement is to clean up your tests. You could just test

results = merge([1, 4, 7], [2, 3, 6, 9])
return results == [1, 2, 3, 4, 6, 7, 9]

Technically this also tests that results is a list, which is arguably an implementation detail, but since that is the obvious choice, it seems fine. (and much terser)

Other than that, this code looks pretty good.