Merge Sort Algorithm

merge_sort.py

def merge_sort(input_list):
    """
    merge_sort is a divide-and-conquer algorithm that repeatedly breaks
    down the large task of sorting into smaller sub-problems that are
    much easier given the following insight:

    Insight 1: If the list only contains 1 element, it's already sorted.
    Insight 2: If you have two lists that are already sorted, you can merge
               the two sorted lists to create a larger sorted list.

               Given two sorted arrays, [2] and [1], you can merge them into
               a single larger array with a simple comparison, creating [1, 2]
    """
    if len(input_list) <= 1:
        # If the input contains 0 or 1 elements, it's already sorted!
        return input_list

    # Split the input in half
    middle_item = len(input_list) // 2

    left_half = merge_sort(input_list[:middle_item])
    right_half = merge_sort(input_list[middle_item:])

    # To create the sorted list, we merge the two smaller sorted lists together
    sorted_list = merge_lists(left_half, right_half)

    return sorted_list


def merge_lists(left, right):
    """
    merge takes two sorted lists (left and right) and merges them
    into a single sorted list
    """
    merged = []

    l_index = 0
    r_index = 0

    while l_index < len(left) and r_index < len(right):
        if left[l_index] <= right[r_index]:
            # The first item in the left list is smaller
            merged.append(left[l_index])
            l_index += 1 # increment the left index to walk the list
        else:
            # The first item in the right list is smaller
            merged.append(right[r_index])
            r_index += 1 # increment the right index to walk the list

    # Whoa there! The left and right lists might not be the same size.

    # Since there's only one list left and we know that it's sorted, we can append
    # the remainder of that list to the merged list (and it will still be sorted)

    # Python syntax lets us concatenate lists by adding them together.
    if left:
        merged = merged + left[l_index:]
    if right:
        merged = merged + right[r_index:]

    # merged contains all of the elements of left and right in sorted order
    return merged