Simple merge sort demonstration with some explanation

mergesort.py

def mergeSort(sorting, first, last):
    """Recursive merge sort function that takes the indices of the 
    first and last values that are being sorted in this pass and methodically 
    splits down the `sorting` list, until it can start remerging the halves.

    Recursion is the only way that merge sort makes sense. It's pretty neat.
    """

    if first >= last:
        # If the first and last pointers are the same or switched, we're done
        return sorting
    else:
        # Find the middle value 
        middle = (last+first) // 2 

        #print("Splitting & sorting the right half from {} to {}".format(first, middle)
        sorting = mergeSort(sorting, first, middle)
        #print("Splitting & sorting the left half from {} to {}".format(middle+1, last)
        sorting = mergeSort(sorting, middle+1, last)
        
        return mergeHalves(sorting, first, middle, last)



def mergeHalves(sorting, first, middle, last):
    """Merges two halves of the `sorting` list at the given points, and since 
    they should each be sorted, the merging just involves picking off which 
    of the next available items from the left or right half is smaller. 

    The merging stops when the end of one half has been reached. At that point we 
    know that the rest of the non-used-up half must be greater than all of the 
    used-up half. 

    Since the remains values are sorted, we just have to add them to the end of 
    the `sorted_list` array; i.e. no further work/ sorting required.
    """

    left_start = first
    left_end = middle
    left_i = left_start         # Index for the position in the left half

    right_start = middle + 1
    right_end = last
    right_i = right_start       # Index for the position in the right half

    print("Merging:\n   ", 
            sorting[left_start:left_end+1],
            sorting[right_start:right_end+1]
            )

    sorted_list = []
    
    while left_i <= left_end and right_i <= right_end:
        # Place in the smallest value
        if sorting[left_i] < sorting[right_i]:
            # Append the next item in the left half if it is smaller
            sorted_list.append(sorting[left_i])

            left_i += 1
        else:
            # Append the next item in the right half if it is smaller
            sorted_list.append(sorting[right_i])

            right_i += 1

    # Once the bounds are met for one half, fill in the rest
    #   => Note that either the left half has some values left OR the right half
    #      It can't be both.
    sorted_list += sorting[left_i:left_end+1]
    sorted_list += sorting[right_i:right_end+1]

    print("    Merged result:\n      ", 
            sorted_list
            )

    # Replace the relevant value in the list
    sorting[first:last+1] = sorted_list
    
    print("    List state (done up to index", last,
            "):\n      ", 
            sorting
            )

    return sorting


if __name__ == "__main__":
    import random

    print("Merge sort demo with Python. At each stage of merging, the "
            "two parts of the list are shown, as well as the final "
            "product and the entire list's state.")

    mode = input("Would you like to contruct a list [C] or generate a random "
                    "one [R]? [C/R] ")
    
    if mode == "C":
        print("Enter numerical values, and then keyboard interrupt (Ctl-C) when "
                "you're done.")
        try:
            unsorted = []

            while True:
                unsorted += [int(input("Number: "))]
        except KeyboardInterrupt:
            pass

    elif mode == "R":
        length = int(input("How long should the array be? "))
        high   = int(input("What's the max value? "))

        unsorted = random.sample(range(high), length)


    print("\n\nYour list:", unsorted, "\n\n")
    print("The algorithm uses divide and conquer to sort the smallest possible "
            "amount first and then work upwards (shown by the increasing size of "
            "the parts to be merged.\n")

    print("Merging two parts of the list is a simple sort where we take whichever "
            "value is least from the front of both of the input lists (which are "
            "already sorted, making it possible to take the value from the front)"
            ".\n")

    print("You can add some extra `print(...)` calls into the code and rerun "
            "if you'd like to see the steps involved in breaking down the list "
            "so that it's small enough to merge at each point.\n\n")

    print("\n\nYour list:", unsorted, "\n\n")