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]) =&gt; [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] &lt; 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) &lt; len(items1) + len(items2):
        left_item = items1[left_pointer]
        right_item = items2[right_pointer]
        if left_item &lt; right_item:
            sorted_list.append(left_item)
            left_pointer += 1
        else:
            sorted_list.append(right_item)
            right_pointer += 1

        if right_pointer &gt;= len(items2):
            sorted_list.extend(items1[left_pointer:])
            break
        if left_pointer &gt;= 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 &lt; other.x
    def __str__(self):
        return "LTO (%d, %d)" % (self.x, self.y)
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 &gt;= len(items2):
    sorted_list.extend(items1[left_pointer:])
    break
if left_pointer &gt;= 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] &lt; right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result + left + right