I wanted to share a bit about how to implement your merge sort. Merge sort is a divide and conquer algorithm that breaks down an array into smaller pieces and eventually pieces them back together one by one sorting the data as it does so. Merging the elements together takes n time for each level that is merged. Each level of the array is half the size of the level below it, just like in a binary search. Because the problem is cut in half each time, it will take log n levels to get to the top level.
def merge(items1, items2):
"""Merge given lists of items, each assumed to already be in sorted order,
and return a new list containing all items in sorted order."""
# Repeat until one list is empty
# Find minimum item in both lists and append it to new list
# Append remaining items in non-empty list to new list
left_pointer = 0
right_pointer = 0
sorted_list = []
while (left_pointer < len(items1)) and (right_pointer < 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
for index in range(right_pointer, len(items2)):
sorted_list.append(items2[index])
return sorted_list
def merge_sort(items):
"""Sort given items by splitting list into two approximately equal halves,
sorting each recursively, and merging results into a list in sorted
"""
# Split items list into approximately equal halves
# Sort each half by recursively calling merge sort
# Merge sorted halves into one list in sorted order
if len(items) < 2:
return
pivot = len(items) // 2
left = items[:pivot]
right = items[pivot:]
# Sort each half by recursively calling merge sort
merge_sort(left) # O(log n)
merge_sort(right) # O(log n)
items[:] = merge(left, right) # O(2n)
return items
I also include my merge sort unit-testing and it passes all tests:
#!python
import unittest
# Change this variable to the sort function you want to test
sort = merge_sort
class IsSortedTest(unittest.TestCase):
def test_is_sorted_on_sorted_integers(self):
# Positive test cases (examples) with lists of sorted integers
assert is_sorted([]) # Empty lists are vacuously sorted
assert is_sorted([3]) # Single item is trivially sorted
assert is_sorted([3, 3]) # Duplicate items are in order
assert is_sorted([3, 5])
assert is_sorted([3, 5, 7])
# TODO: Write more positive test cases with assert statements
assert is_sorted([-4, -3, -2, -1])
assert is_sorted([-4, -4, -4, -4])
assert is_sorted([-4, 0, 4])
assert is_sorted([-4, 0, -0, 4])
def test_is_sorted_on_unsorted_integers(self):
# Negative test cases (counterexamples) with lists of unsorted integers
assert not is_sorted([5, 3]) # is False
assert not is_sorted([3, 5, 3]) # is False
assert not is_sorted([7, 5, 3]) # is False
# TODO: Write more negative test cases with assert # is False statements
assert not is_sorted([-11, 3, 2]) # is False
assert not is_sorted([2, -1, 1, 1]) # is False
assert not is_sorted([4, -3, 2, -1]) # is False
def test_is_sorted_on_sorted_strings(self):
# Positive test cases (examples) with lists of sorted strings
assert is_sorted(['A']) # Single item is trivially sorted
assert is_sorted(['A', 'A']) # Duplicate items are in order
assert is_sorted(['A', 'B'])
assert is_sorted(['A', 'B', 'C'])
# TODO: Write more positive test cases with assert statements
# You'll need a lot more than this to test sorting algorithm robustness
# lowercase
assert is_sorted(['a', 'b', 'c'])
assert is_sorted(['a', 'a', 'c'])
# Mixed
assert is_sorted(['A', 'a', 'b'])
assert is_sorted(['C', 'a', 'b'])
# Testing Multiple
assert is_sorted(['AA', 'BB', 'CC'])
assert is_sorted(['AA', 'BA', 'CA'])
assert is_sorted(['AAAA', 'BB', 'CCC'])
assert is_sorted(['AA', 'AAA', 'AAAA'])
def test_is_sorted_on_unsorted_strings(self):
# Negative test cases (counterexamples) with lists of unsorted strings
assert not is_sorted(['B', 'A']) # is False
assert not is_sorted(['A', 'B', 'A']) # is False
assert not is_sorted(['C', 'B', 'A']) # is False
# TODO: 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 is_sorted(['CCC', 'BBB', 'AAA']) # is False
assert not is_sorted(['CCCC', 'CCC', 'C']) # is False
# Lowercase
assert not is_sorted(['c', 'b', 'a']) # is False
assert not is_sorted(['c', 'c', 'a']) # is False
def test_is_sorted_on_sorted_tuples(self):
# Positive test cases (examples) with lists of sorted tuples
assert is_sorted([(3, 5)]) # Single item
assert is_sorted([(3, 'A')]) # Single item
assert is_sorted([('A', 3)]) # Single item
assert is_sorted([('A', 'B')]) # Single item
assert is_sorted([(3, 5), (3, 5)]) # Duplicate items
assert is_sorted([(3, 'A'), (3, 'A')]) # Duplicate items
assert is_sorted([('A', 3), ('A', 3)]) # Duplicate items
assert is_sorted([('A', 'B'), ('A', 'B')]) # Duplicate items
assert is_sorted([('A', 3), ('B', 5)]) # Both items sorted
assert is_sorted([('A', 3), ('B', 3)]) # First item sorted
assert is_sorted([('A', 3), ('A', 5)]) # Second item sorted
assert is_sorted([(3, 'A'), (5, 'B')]) # Both items sorted
assert is_sorted([(3, 'A'), (5, 'A')]) # First item sorted
assert is_sorted([(3, 'A'), (3, 'B')]) # Second item sorted
# TODO: Write more positive test cases with assert statements
# ...
def test_is_sorted_on_unsorted_tuples(self):
# Negative test cases (counterexamples) with lists of unsorted tuples
assert not is_sorted([(5, 'B'), (3, 'A')]) # is False # Both items unsorted
assert not is_sorted([(5, 'A'), (3, 'B')]) # is False # First item unsorted
assert not is_sorted([(3, 'B'), (3, 'A')]) # is False # Second item unsorted
assert not is_sorted([('B', 5), ('A', 3)]) # is False # Both items unsorted
assert not is_sorted([('B', 3), ('A', 5)]) # is False # First item unsorted
assert not is_sorted([('A', 5), ('A', 3)]) # is False # Second item unsorted
# TODO: Write more negative test cases with assert # is False statements
# ...
class IntegerSortTest(unittest.TestCase):
def test_sort_on_empty_list(self):
items = []
sort(items)
assert items == [] # List should not be changed
def test_sort_on_small_lists_of_integers(self):
items1 = [3]
sort(items1)
assert items1 == [3] # List should not be changed
items2 = [5, 3]
sort(items2)
assert items2 == [3, 5] # List should be in sorted order
items3 = [5, 7, 3]
sort(items3)
assert items3 == [3, 5, 7]
# TODO: Write more test cases with assert equal list statements
# You'll need a lot more than this to test sorting algorithm robustness
# ...
def test_sort_on_small_lists_of_integers_with_duplicates(self):
items1 = [3, 3]
sort(items1)
assert items1 == [3, 3] # List should not be changed
items2 = [3, 5, 3]
sort(items2)
assert items2 == [3, 3, 5] # List should be in sorted order
items3 = [5, 5, 3, 5, 3]
sort(items3)
assert items3 == [3, 3, 5, 5, 5]
items4 = [7, 5, 3, 7, 5, 7, 5, 3, 7]
sort(items4)
assert items4 == [3, 3, 5, 5, 5, 7, 7, 7, 7]
# TODO: Create lists of integers with many duplicate values
# TODO: Write more test cases with assert equal list statements
def test_sort_on_lists_of_random_integers(self):
# Generate list of 10 random integers from range [1...20]
items1 = random_ints(10, 1, 20)
sorted_items1 = sorted(items1) # Create a copy of list in sorted order
sort(items1) # Call mutative sort function to sort list items in place
assert items1 == sorted_items1
# Generate list of 20 random integers from range [1...50]
items2 = random_ints(20, 1, 50)
sorted_items2 = sorted(items2) # Copy
sort(items2) # Mutate
assert items2 == sorted_items2
# Generate list of 30 random integers from range [1...100]
items3 = random_ints(30, 1, 100)
sorted_items3 = sorted(items3) # Copy
sort(items3) # Mutate
assert items3 == sorted_items3
def test_sort_on_lists_of_random_integers_with_duplicates(self):
# Generate list of 20 random integers from range [1...10]
items1 = random_ints(20, 1, 10)
sorted_items1 = sorted(items1) # Create a copy of list in sorted order
sort(items1) # Call mutative sort function to sort list items in place
assert items1 == sorted_items1
# Generate list of 50 random integers from range [1...20]
items2 = random_ints(50, 1, 20)
sorted_items2 = sorted(items2) # Copy
sort(items2) # Mutate
assert items2 == sorted_items2
# Generate list of 100 random integers from range [1...30]
items3 = random_ints(100, 1, 30)
sorted_items3 = sorted(items3) # Copy
sort(items3) # Mutate
assert items3 == sorted_items3
class StringSortTest(unittest.TestCase):
def test_sort_on_small_lists_of_strings(self):
items1 = ['A']
sort(items1)
assert items1 == ['A'] # List should not be changed
items2 = ['B', 'A']
sort(items2)
assert items2 == ['A', 'B'] # List should be in sorted order
items3 = ['B', 'C', 'A']
sort(items3)
assert items3 == ['A', 'B', 'C']
# TODO: Write more test cases with assert equal list statements
# You'll need a lot more than this to test sorting algorithm robustness
# ...
def test_sort_on_fish_book_title(self):
items = 'one fish two fish red fish blue fish'.split()
sorted_items = sorted(items) # Create a copy of list in sorted order
sort(items) # Call mutative sort function to sort list items in place
assert items == sorted_items
def test_sort_on_seven_dwarf_names(self):
items = 'Doc Grumpy Happy Sleepy Bashful Sneezy Dopey'.split()
sorted_items = sorted(items) # Copy
sort(items) # Mutate
assert items == sorted_items
if __name__ == '__main__':
unittest.main()
