# Merge two sorted lists in Python

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"
"            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)

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

# 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

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

• I'm glad that you are able to point out the edge cases that I need to handle. Good tests. Jul 30, 2018 at 18:20

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.