# merge_sort and unit testing

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

[] -> [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()  # 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()

• in python 3, min(10,None) fails. You cannot compare integers and None. Your next(xs,None) call can return None. – Jean-François Fabre Apr 29 '18 at 9:34

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