Merge Sort

Known to John von Neumann in 1945, 70+ years ago

Step 0- Testing utilities

Take a look at resources/utils.py if you're curious.



In [129]:

    
import random
random.seed(0)
from resources.utils import run_tests

Step 1- split

Given a list let's split it into two lists right down the middle



In [65]:

    
def split(input_list):
    """
    Splits a list into two pieces
    :param input_list: list
    :return: left and right lists (list, list)
    """
    input_list_len = len(input_list)
    midpoint = input_list_len // 2
    return input_list[:midpoint], input_list[midpoint:]



In [100]:

    
tests_split = [
    ({'input_list': [1, 2, 3]}, ([1], [2, 3])),
    ({'input_list': [1, 2, 3, 4]}, ([1, 2], [3, 4])),
    ({'input_list': [1, 2, 3, 4, 5]}, ([1, 2], [3, 4, 5])),
    ({'input_list': [1]}, ([], [1])),
    ({'input_list': []}, ([], []))
]



In [101]:

    
run_tests(tests_split, split)









    



✓ All tests successful

Step 2- merge sorted lists

Given two sorted lists we should be able to "merge" them into a single list as a linear operation



In [93]:

    
def merge_sorted_lists(list_left, list_right):
    """
    Merge two sorted lists
    This is a linear operation
    O(len(list_right) + len(list_right))
    :param left_list: list
    :param right_list: list
    :return merged list
    """
    # Special case: one or both of lists are empty
    if len(list_left) == 0:
        return list_right
    elif len(list_right) == 0:
        return list_left
    
    # General case
    index_left = index_right = 0
    list_merged = []  # list to build and return
    list_len_target = len(list_left) + len(list_right)
    while len(list_merged) < list_len_target:
        if list_left[index_left] <= list_right[index_right]:
            # Value on the left list is smaller (or equal so it should be selected)
            list_merged.append(list_left[index_left])
            index_left += 1
        else:
            # Right value bigger
            list_merged.append(list_right[index_right])
            index_right += 1
            
        # If we are at the end of one of the lists we can take a shortcut
        if index_right == len(list_right):
            # Reached the end of right
            # Append the remainder of left and break
            list_merged += list_left[index_left:]
            break
        elif index_left == len(list_left):
            # Reached the end of left
            # Append the remainder of right and break
            list_merged += list_right[index_right:]
            break
        
    return list_merged



In [94]:

    
tests_merged_sorted_lists = [
    ({'list_left': [1, 5], 'list_right': [3, 4]}, [1, 3, 4, 5]),
    ({'list_left': [5], 'list_right': [1]}, [1, 5]),
    ({'list_left': [], 'list_right': []}, []),
    ({'list_left': [1, 2, 3, 5], 'list_right': [4]}, [1, 2, 3, 4, 5]),
    ({'list_left': [1, 2, 3], 'list_right': []}, [1, 2, 3]),
    ({'list_left': [1], 'list_right': [1, 2, 3]}, [1, 1, 2, 3]),
    ({'list_left': [1, 1], 'list_right': [1, 1]}, [1, 1, 1, 1]),
    ({'list_left': [1, 1], 'list_right': [1, 2]}, [1, 1, 1, 2]),
    ({'list_left': [3, 3], 'list_right': [1, 4]}, [1, 3, 3, 4]),
]



In [95]:

    
run_tests(tests_merged_sorted_lists, merge_sorted_lists)









    



✓ All tests successful

Step 3- merge sort

Merge sort only needs to utilize the previous 2 functions
We need to split the lists until they have a single element
A list with a single element is sorted (duh)
Now we can merge these single-element (or empty) lists



In [127]:

    
def merge_sort(input_list):
    if len(input_list) <= 1:
        return input_list
    else:
        left, right = split(input_list)
        # The following line is the most important piece in this whole thing
        return merge_sorted_lists(merge_sort(left), merge_sort(right))



In [125]:

    
random_list = [random.randint(1, 1000) for _ in range(100)]
tests_merge_sort = [
    ({'input_list': [1, 2]}, [1, 2]),
    ({'input_list': [2, 1]}, [1, 2]),
    ({'input_list': []}, []),
    ({'input_list': [1]}, [1]),
    ({'input_list': [5, 1, 1]}, [1, 1, 5]),
    ({'input_list': [9, 1, 10, 2]}, [1, 2, 9, 10]),
    ({'input_list': range(10)[::-1]}, list(range(10))),
    ({'input_list': random_list}, sorted(random_list))
]



In [126]:

    
run_tests(tests_merge_sort, merge_sort)









    



✓ All tests successful

Example walk through

merge_sort keeps splitting until we get to single-element lists. Once we're there (the base case of recursion) the callers can start applying merge_sorted_list. For the following example here's what's going on:

input_list=[9, 1, 10, 2]
left=[9, 1] and right=[10, 2]
merge_sort([9, 1]) is responsible for sorting [9, 1], let's call it L1.
merge_sort([10, 2]) is reponsible for sorting [10, 2], let's call it R1.

For L1:

left=[9] and right=[1]
merge_sort([9]) returns [9] since it's the base case and merge_sort([1]) returns [1]
merge_sorted_lists([9], [1]) returns [1, 9] which is sorted

Same thing happens for R1 and the result is [2, 10]. Now merge_sorted_lists(L1, R1) returns the final answer.