MergeSort implementation in Python

Question

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

• coderodde: You can make it run faster: codereview.stackexchange.com/questions/149722/…

Answer 1

• You seem to assume that at the end of merge loop the items1 list is always empty. It is not necessarily so.

• The most important feature of merge sort is stability: items compared equal retain their order. In other words, if the items compare equal you want to merge the left_item first. The left_item < right_item loses it.

• A comment in

   merge_sort(left) # O(log n)
  

  is misleading. This step takes O(n log n).