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)

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

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.