3
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ In the tests, I can't see any reason to avoid simple list equality: e.g. results == [1,2,3,4,6,7,9] \$\endgroup\$ – Josiah Jul 29 '18 at 21:42
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I'm glad that you are able to point out the edge cases that I need to handle. Good tests. \$\endgroup\$ – NinjaG Jul 30 '18 at 18:20
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.