# merge sort: split list in half, then sort each half and
# merge the two; this is done recursively
#
# we print the current state of the list each time through
#
# also count (and print) the number of comparisons and
# exchanges
# 
# Matt Bishop   ECS 36A, Winter 2019
#

#
# set this to False to print *only* the original (unsorted)
# and the final (sorted) lists
# set to True to print the intermediate (partially sorted) lists
#
showintermediate = True

#
# we will generate a list of this many numbers
# and then shuffle them 7 times using shuffle()
# from the random module
#
import random
nnums = 20

# set the number of comparisons to 0
compares = 0

# swaps don't really make sense, so we count copies
copies = 0

#
# this is the merge sort routine
#
# if the list is 1 item, you are done
# otherwise, split the list in two parts, sort them independently
# (using mergesort), then merge the two lists
#
def mergesort(numlist):
        # we track the number of comparisons and swaps (exchanges)
        global copies, compares

        # if the list is one number, you're done
        if len(numlist) <= 1:
                # print the current state of the list (visually see the sorting)
                if showintermediate:
                        print("   Merge:", numlist)
                return
        
        # find the midpoint of the list
        mid = len(numlist) // 2

        # split the list into 2 parts, left and right
        # note midpoint in kept in the right half
        left = numlist[:mid]
        right = numlist[mid:]

        # now sort each half
        mergesort(left)
        mergesort(right)

        # here, i indexes left, j indexes right, and
        # k indexes numlist
        # left and right aremerged; their sorted merge
        # is put in numlist
        # start everything at the beginning of the lists
        i = j = k = 0

        # this part does the merge
        # compare first element of left with first element
        # of right; put the smaller into numlist and advance
        # the appropriate indices
        while i < len(left) and j < len(right):
                # we do a compare and a copy here
                compares += 1
                copies += 1
                # if left is smaller or equal, put it into numlist
                if left[i] <= right[j]:
                        numlist[k] = left[i]
                        i += 1
                        k += 1
                # if right is smaller, put it into numlist
                elif left[i] > right[j]:
                        numlist[k] = right[j]
                        j += 1
                        k += 1
        # at this point, either i or j is at the end so
        # only one of the following while loops has its
        # body executed
        while i < len(left):
                # a copy
                copies += 1
                # add next element of left to the end of numlist
                numlist[k] = left[i]
                i += 1
                k += 1
        while j < len(right):
                # a copy
                copies += 1
                # add next element of left to the end of numlist
                numlist[k] = right[j]
                j += 1
                k += 1

        # print the current state of the list (visually see the sorting)
        if showintermediate:
                print("   Merge:", numlist)

#
# generate a list of numbers
# we just put the first nnums number into a list (0 .. nnums-1)
# and then shuffle it 7 times
#
def loadnums():
        # generate the list; use range and convert it
        numlist = list(range(nnums))

        # now shuffle 7 times; in theory, this makes
        # it as random as possible
        for i in range(0, 7):
                random.shuffle(numlist)
                
        # and return the list!
        return numlist

#
# this puts it all together
#
def main():
        # we need to print these
        global compares, copies
        
        # get the list
        # if it's empty, quit (just in case :)
        nums = loadnums()
        if nums == []:
                return

        # print the initial list
        print("Unsorted:", nums)
        
        # sort the list
        mergesort(nums)

        # print the sorted list and the relevant statistics
        print("  Sorted:", nums)
        print("This took {} comparisons and {} copies".format(compares, copies))

#
# and we're off!
#
main()