def mergesort(lst):
    # this is an individual element
    if len(lst) == 1: return lst
    
    # find the midpoint
    mid = len(lst)/2
    
    # run mergesort on the left hand side
    left = mergesort(lst[:mid])
    
    # run mergesort on the right hand side
    right = mergesort(lst[mid:])
    
    # merge sorted lists back together
    return merge(left, right)

"""
Explanation: Mergesort
Summary
| Performance                 | Complexity       |
|-----------------------------|------------------|
|Worst-case                   | $O(n\log{n})$       |
|Best-case                    | $O(n\log{n})$           |
|Average                      | $O(n\log{n})$       |
|Worst-case space             | $O(n)$           |
Algorithm
Recursively split list and then recursively merge them together in sorted order. Because the merge is done recursively, starting from the individual elements, the lists being merged together are guaranteed to be sorted.
End of explanation
"""


def merge(left, right):
    # indices into left and right lists
    i = j = 0
    
    # merged list
    result = []
    
    # keep going until we've gone over every element within the list
    while i < len(left) or j < len(right):
        if i >= len(left):
            # if left is empty, use right
            result.append(right[j])
            j += 1            
        elif j >= len(right):
            # if right is empty, use left
            result.append(left[i])
            i += 1            
        elif left[i] < right[j]:
            # if left is less than right, use left
            result.append(left[i])
            i += 1
        else:
            # otherwise use right
            result.append(right[j])
            j += 1
            
    return result

"""
Explanation: and to merge the lists back together, we just have to iterate over both lists picking whichever list has the smallest item. To do so, we'll keep two indices: i and j. It's possible one list is larger than the other (i.e. if the list is odd, then when split it will give two differently sized lists):
End of explanation
"""


merge_sort_example([5, 2, 1, 20, 10, 3, 4, 80])

"""
Explanation: Animation of mergesort:
End of explanation
"""


lst = [5, 2, 1, 20, 10, 3, 4, 80, 0]
sorted_list = mergesort(lst)
print(sorted_list)

"""
Explanation: Let's try out our code:
End of explanation
"""


