merge_sort and unit testing

Question

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

• Jean-François Fabre: in python 3, min(10,None) fails. You cannot compare integers and None. Your next(xs,None) call can return None.

Answer 1

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