2
\$\begingroup\$

I made a merge sort and wanted to ask for code review. It passed all of the unit testing. The idea behind the classic Mergesort algorithm is to divide an array in half, sort each half, and merge the two halves into a single sorted list.

Examples:

merge_sort([2,7,5,9,8,9]) -> [2,5,7,8,9,9]

merge_sort()([7,1,8,2]) -> [1,2,7,8]

merge_sort()([2]) -> [2]

[] -> [Empty] list 

Merge sort

def merge(xs, ys):
    xs, ys = iter(xs), iter(ys)
    x,  y  = next(xs,None), next(ys,None)
    while x and y:
        yield min(x,y)
        if x <= y: x = next(xs, None)
        else:      y = next(ys, None)

    # Yield remaining items from whichever list isn't empty
    yield [x,y][x is None]
    for item in [xs,ys][x is None]: yield item

def merge_sort(xs):
    # from heapq import merge
    if len(xs) < 2:
        return xs

    mid = len(xs)/2
    return list(merge(merge_sort(xs[:mid]), merge_sort(xs[mid:])))



# unit testing

#!python

from merge_sort import quicksort

from sorting import merge_sort
import unittest

# Change this variable to the sort function you want to test
is_sort = quick_sort2


class IsSortedTest(unittest.TestCase):
    def test_merge_sort_on_sorted_integers(self):
        # Positive test cases (examples) with lists of sorted integers
        assert merge_sort([])  # Empty lists are vacuously sorted
        assert merge_sort([3])  # Single item is trivially sorted
        assert merge_sort([3, 3])  # Duplicate items are in order
        assert merge_sort([3, 5])
        assert merge_sort([3, 5, 7])
        # : Write more positive test cases with assert  statements
        assert merge_sort([-4, -3, -2, -1])
        assert merge_sort([-4, -4, -4, -4])
        assert merge_sort([-4, 0, 4])
        assert merge_sort([-4, 0, -0, 4])

    def test_merge_sort_on_unsorted_integers(self):
        # Negative test cases (counterexamples) with lists of unsorted integers
        assert not merge_sort([5, 3])  # is False
        assert not merge_sort([3, 5, 3])  # is False
        assert not merge_sort([7, 5, 3])  # is False
        # : Write more negative test cases with assert # is False statements
        assert not merge_sort([-11, 3, 2])  # is False
        assert not merge_sort([2, -1, 1, 1])  # is False
        assert not merge_sort([4, -3, 2, -1])  # is False

    def test_merge_sort_on_sorted_strings(self):
        # Positive test cases (examples) with lists of sorted strings
        assert merge_sort(['A'])  # Single item is trivially sorted
        assert merge_sort(['A', 'A'])  # Duplicate items are in order
        assert merge_sort(['A', 'B'])
        assert merge_sort(['A', 'B', 'C'])
        # : Write more positive test cases with assert  statements
        # You'll need a lot more than this to test sorting algorithm robustness
        # lowercase
        assert merge_sort(['a', 'b', 'c'])
        assert merge_sort(['a', 'a', 'c'])
        # Mixed
        assert merge_sort(['A', 'a', 'b'])
        assert merge_sort(['C', 'a', 'b'])
        # Testing Multiple
        assert merge_sort(['AA', 'BB', 'CC'])
        assert merge_sort(['AA', 'BA', 'CA'])
        assert merge_sort(['AAAA', 'BB', 'CCC'])
        assert merge_sort(['AA', 'AAA', 'AAAA'])

    def test_merge_sort_on_unsorted_strings(self):
        # Negative test cases (counterexamples) with lists of unsorted strings
        assert not merge_sort(['B', 'A'])  # is False
        assert not merge_sort(['A', 'B', 'A'])  # is False
        assert not merge_sort(['C', 'B', 'A'])  # is False
        # : Write more negative test cases with assert # is False statements
        # You'll need a lot more than this to test sorting algorithm robustness
        # Multiple
        assert not merge_sort(['CCC', 'BBB', 'AAA'])  # is False
        assert not merge_sort(['CCCC', 'CCC', 'C'])  # is False
        # Lowercase
        assert not merge_sort(['c', 'b', 'a'])  # is False
        assert not merge_sort(['c', 'c', 'a'])  # is False

    def test_merge_sort_on_sorted_tuples(self):
        # Positive test cases (examples) with lists of sorted tuples
        assert merge_sort([(3, 5)])  # Single item
        assert merge_sort([(3, 'A')])  # Single item
        assert merge_sort([('A', 3)])  # Single item
        assert merge_sort([('A', 'B')])  # Single item
        assert merge_sort([(3, 5), (3, 5)])  # Duplicate items
        assert merge_sort([(3, 'A'), (3, 'A')])  # Duplicate items
        assert merge_sort([('A', 3), ('A', 3)])  # Duplicate items
        assert merge_sort([('A', 'B'), ('A', 'B')])  # Duplicate items
        assert merge_sort([('A', 3), ('B', 5)])  # Both items sorted
        assert merge_sort([('A', 3), ('B', 3)])  # First item sorted
        assert merge_sort([('A', 3), ('A', 5)])  # Second item sorted
        assert merge_sort([(3, 'A'), (5, 'B')])  # Both items sorted
        assert merge_sort([(3, 'A'), (5, 'A')])  # First item sorted
        assert merge_sort([(3, 'A'), (3, 'B')])  # Second item sorted
        # : Write more positive test cases with assert  statements
        # ...

    def test_merge_sort_on_unsorted_tuples(self):
        # Negative test cases (counterexamples) with lists of unsorted tuples
        assert not merge_sort([(5, 'B'), (3, 'A')])  # is False  # Both items unsorted
        assert not merge_sort([(5, 'A'), (3, 'B')])  # is False  # First item unsorted
        assert not merge_sort([(3, 'B'), (3, 'A')])  # is False  # Second item unsorted
        assert not merge_sort([('B', 5), ('A', 3)])  # is False  # Both items unsorted
        assert not merge_sort([('B', 3), ('A', 5)])  # is False  # First item unsorted
        assert not merge_sort([('A', 5), ('A', 3)])  # is False  # Second item unsorted
        # : Write more negative test cases with assert # is False statements
        # ...



if __name__ == '__main__':
    unittest.main()
\$\endgroup\$
  • \$\begingroup\$ in python 3, min(10,None) fails. You cannot compare integers and None. Your next(xs,None) call can return None. \$\endgroup\$ – Jean-François Fabre Apr 29 '18 at 9:34
1
\$\begingroup\$
while x and y:
    yield min(x,y)
    if x <= y: x = next(xs, None)
    else:      y = next(ys, None)

This is correct. Note, however, that it is relying on the stability guarantee of min to ensure that if two objects are equal, the one that is yielded is the same as the one that gets updated. This is quite a subtle assumption.

I personally would rather bring the yield inside the if block for clarity. It would also avoid testing the comparison twice, which for sorting some data types can be a moderately expensive operation.

while x and y:
    if x <= y:
         yield x
         x = next(xs, None)
    else:
         yield y
         y = next(ys, None)

Both

from merge_sort import quicksort

and

is_sort = quick_sort2

look confusing. What is quicksort doing here? I suspect that this is leftover code that needs cleaning up.


Your test cases show a good spread of general and special cases, across a range of data types. I would suggest a few tests of object types, and especially objects that are equal according to their comparison function but distinguishable otherwise. For example

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)

As referenced earlier, these help check the stability of the sort (That equal objects remain in the same order relative to each other as they were in the unsorted list) and the correctness (specifically, that the sorted list does contain the same elements as the input).


I am not familiar with this way of writing Python tests. That means I can't say much more than that it looks weird. I would have expected test cases to specify the desired output of the function. Perhaps something like

assertEqual(merge_sort([3, 7, 5]), [3, 5, 7])
\$\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.