Merge sort sample

'''
This version prints indicators of its progress as it runs. To make this work, temporary variables are created for unsorted lists so they can be printed.
'''
def mergesort(lst):

    #Then, what does it do? mergesort should recursively run mergesort on the left and right sides of lst until it's given a list of only one item. So, if lst has only one item, we should just return that one-item list.

    if len(lst) <= 1:
        print("Returning one-item list:", lst)
        return lst

    #Otherwise, we should call mergesort separately on the left and right sides. Since each successive call to mergesort sends half as many items, we're guaranteed to eventually send it a list with only one item, at which point we'll stop calling mergesort again.
    else:
        #Floor division on the length of the list will find us the index of the middle value.
        midpoint = len(lst) // 2

        #lst[:midpoint] will get the left side of the list based on list slicing syntax. So, we want to sort the left side of the list alone and assign the result to the new smaller list left.
        unsortedleft = lst[:midpoint]
        unsortedright = lst[midpoint:]

        print("Sorting left:", unsortedleft)
        left = mergesort(lst[:midpoint])
        print("Left sorted:", left)

        #And same for the right side.
        print("Sorting right:", unsortedright)
        right = mergesort(lst[midpoint:])
        print("Right sorted:", right)

'''
So, left and right now hold sorted lists of each half of the original list. They might each have only one item, or they could each have several items. Now we want to compare the first items in each list one-by-one, adding the smaller to our new result list until one list is completely empty.
'''
        print("Merging", left, "and", right)
        newlist = []
        while len(left) and len(right) > 0:

            #If the first number in left is lower, add it to the new list and remove it from left
            if left[0] < right[0]:
                newlist.append(left[0])
                del left[0]

            #Otherwise, add the first number from right to the new list and remove it from right
            else:
                newlist.append(right[0])
                del right[0]

        #When the while loop above is done, it means one of the two lists is empty. Because both lists were sorted, we can now add the remainder of each list to the new list. The empty list will have no items to add, and the non-empty list will add its items in order.

        newlist.extend(left)
        newlist.extend(right)

        #newlist is now the sorted version of lst! So, we can return it. If this was a recursive call to mergesort, then this sends a sorted half- list up the ladder. If this was the original call, then this is the final sorted list.

        print("Returning merged list:", newlist)
        return newlist

print(mergesort([2, 5, 3, 8, 6, 9, 1, 4, 7]))

#Total iterations = 8 (see Returning merged list)
'''
Output will show:
Sorting left: [2, 5, 3, 8]
Sorting left: [2, 5]
Sorting left: [2]
Returning one-item list: [2]
Left sorted: [2]
Sorting right: [5]
Returning one-item list: [5]
Right sorted: [5]
Merging [2] and [5]
Returning merged list: [2, 5]
Left sorted: [2, 5]
Sorting right: [3, 8]
Sorting left: [3]
Returning one-item list: [3]
Left sorted: [3]
Sorting right: [8]
Returning one-item list: [8]
Right sorted: [8]
Merging [3] and [8]
Returning merged list: [3, 8]
Right sorted: [3, 8]
Merging [2, 5] and [3, 8]
Returning merged list: [2, 3, 5, 8]
Left sorted: [2, 3, 5, 8]
Sorting right: [6, 9, 1, 4, 7]
Sorting left: [6, 9]
Sorting left: [6]
Returning one-item list: [6]
Left sorted: [6]
Sorting right: [9]
Returning one-item list: [9]
Right sorted: [9]
Merging [6] and [9]
Returning merged list: [6, 9]
Left sorted: [6, 9]
Sorting right: [1, 4, 7]
Sorting left: [1]
Returning one-item list: [1]
Left sorted: [1]
Sorting right: [4, 7]
Sorting left: [4]
Returning one-item list: [4]
Left sorted: [4]
Sorting right: [7]
Returning one-item list: [7]
Right sorted: [7]
Merging [4] and [7]
Returning merged list: [4, 7]
Right sorted: [4, 7]
Merging [1] and [4, 7]
Returning merged list: [1, 4, 7]
Right sorted: [1, 4, 7]
Merging [6, 9] and [1, 4, 7]
Returning merged list: [1, 4, 6, 7, 9]
Right sorted: [1, 4, 6, 7, 9]
Merging [2, 3, 5, 8] and [1, 4, 6, 7, 9]
Returning merged list: [1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
'''