<jupyter_start><jupyter_text>MergeSortMergeSort is a *divide and conquer* algorithm that divides a list into equal halves until it has two single elements and then merges the sub-lists until the entire list has been reassembled in order. DivideOur MergeSort code will focus first on the divide portion of the algorithm. If the list we receive has only a single element in it, the list can be considered sorted and we can return immediately.  This is our recursion base case.  If we have more than 1 element we need to split the list into equal halves and call MergeSort again for each half. ConquerOnce you have split the list down to single elements, your mergesort will start merging lists, in order, until you have reassembled the entire list in order. DesignFirst, let's sketch this out. It's clear we want a recursive function, but how will it govern its recursion?```pythondef mergesort(items):     Base case, a list of 0 or 1 items is already sorted    if len(items) <= 1:        return items         Otherwise, find the midpoint and split the list     TODO     left =     right =         Call mergesort recursively with the left and right half    left = mergesort(left)    right = mergesort(right)         Merge our two halves and return    return merge(left, right)    def merge(left, right):     Given two ordered lists, merge them together in order,     returning the merged list.     TODO```We have decomposed the problem, now we will address each piece separately. DivideWe can use python's `//` operator to find a midpoint. If `items`'s length is even, we will have the midpoint. If `items`'s length is odd, we will have one half larger by one.<jupyter_code>list1 = [0, 1, 2, 3]
midpoint1 = len(list1) // 2
print('List 1 midpoint: {}'.format(midpoint1))

list2 = [4, 5, 6]
midpoint2 = len(list2) // 2
print('List 2 midpoint: {}'.format(midpoint2))<jupyter_output>List 1 midpoint: 2
List 2 midpoint: 1<jupyter_text>With our midpoints, we can slice the lists using python's special notation. Note, you can improve effencncy by not using the slice function. Instead, keep track of indicies.<jupyter_code>left1 = list1[:midpoint1]
right1 = list1[midpoint1:]
print('List 1 left side: {}'.format(left1))
print('List 1 right side: {}'.format(right1))

left2 = list2[:midpoint2]
right2 = list2[midpoint2:]
print('List 2 left side: {}'.format(left2))
print('List 2 right side: {}'.format(right2))<jupyter_output><empty_output><jupyter_text>That addresses our first TODO, now for the fun one.The `merge` function needs to take two sorted lists, and interleave them, yielding a _merged_ sorted list. We can accomplish that by tracking an index into both lists, and once one is exhausted, appending the remaining items from the other list.<jupyter_code>def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0
    
    # Move through the lists until we have exhausted one
    while left_index < len(left) and right_index < len(right):
        # If left's item is larger, append right's item
        # and increment the index
        if left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        # Otherwise, append left's item and increment
        else:
            merged.append(left[left_index])
            left_index += 1
     
    # Append any leftovers. Because we've broken from our while loop,
    # we know at least one is empty, and the remaining:
    # a) are already sorted
    # b) all sort past our last element in merged
    merged += left[left_index:]
    merged += right[right_index:]
        
    # return the ordered, merged list
    return merged

# Test this out
merged = merge([1,3,7], [2,5,6])
print(merged)<jupyter_output><empty_output><jupyter_text>Now we can combine our TODO resolutions into our sketch from above.<jupyter_code>def mergesort(items):

    if len(items) <= 1:
        return items
    
    mid = len(items) // 2
    left = items[:mid]
    right = items[mid:]
    
    left = mergesort(left)
    right = mergesort(right)
    
    return merge(left, right)
    
def merge(left, right):
    
    merged = []
    left_index = 0
    right_index = 0
    
    while left_index < len(left) and right_index < len(right):
        if left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        else:
            merged.append(left[left_index])
            left_index += 1

    merged += left[left_index:]
    merged += right[right_index:]
        
    return merged


test_list_1 = [8, 3, 1, 7, 0, 10, 2]
test_list_2 = [1, 0]
test_list_3 = [97, 98, 99]
print('{} to {}'.format(test_list_1, mergesort(test_list_1)))
print('{} to {}'.format(test_list_2, mergesort(test_list_2)))
print('{} to {}'.format(test_list_3, mergesort(test_list_3)))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0909465869251392, 'fraction_numerical': 0.018148071767374718, 'mean_word_length': 3.457720588235294, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '168780', 'license': 'Unlicense', 'n_tokens_mistral': 1502, 'n_tokens_neox': 1420, 'n_words': 577, 'path': 'Basic Algorithms/Sort Algorithms/merge_sort_walkthrough.ipynb', 'repo_name': 'michal0janczyk/udacity_data_structures_and_algorithms_nanodegree', 'size': '4849'}