2
\$\begingroup\$

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()
\$\endgroup\$
1
\$\begingroup\$
  • 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).

\$\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.