import matplotlib.pyplot as plt
import random
import time

##############################################################
## Selection Sort                                           ##
##############################################################

def selectionSort(mylist):
    n = len(mylist)

    # Consider each starting index except the last, as that
    # will be the maximum element in the list by the time
    # we finish with the second-to-last position
    for startIdx in range(n-1):
        # Find the minimum element of those from startIdx
        # to the end of the list
        minIdx = startIdx
        for i in range(startIdx+1, n):
            if mylist[i] < mylist[minIdx]:
                minIdx = i
        
        # Swap to put the minimum element (of those startIdx->end)
        # in position startIdx
        mylist[startIdx], mylist[minIdx] = mylist[minIdx], mylist[startIdx]

##############################################################
## Merge Sort                                               ##
##############################################################

def mergeSort(mylist):
    n = len(mylist)

    # If the list contains 0 or 1 item, we have no work to do
    if n < 2:
        return

    # First, divide the list into two smaller lists
    m = n // 2
    left, right = mylist[:m], mylist[m:]

    # Next, recursively sort each sublist
    mergeSort(left)
    mergeSort(right)

    # Finally, merge the two sorted sublists back together
    merge(left, right, mylist)

def merge(list1, list2, list3):
    """
    Merge the two sorted lists list1 and list2 into list3.
    """
    # Keep track of current indices into each list
    i1, i2, i3 = 0, 0, 0
    n1, n2 = len(list1), len(list2)

    # Keep merging as long as both list1 and list2 have more items
    while i1 < n1 and i2 < n2:
        if list1[i1] < list2[i2]: # take from list1
            list3[i3] = list1[i1]
            i1 += 1
        else:                     # take from list2
            list3[i3] = list2[i2]
            i2 += 1

        i3 += 1

    # At least one of the lists is empty, so grab the remaining elements
    while i1 < n1:
        list3[i3] = list1[i1]
        i1 += 1
        i3 += 1
        
    while i2 < n2:
        list3[i3] = list2[i2]
        i2 += 1
        i3 += 1

##############################################################
## Timing Sorts                                             ##
##############################################################

def timeSorts():
    nvals = [10, 20, 40, 60, 80, 100, 200, 500, 1000, 2000]
    selectionTimes = []
    mergeTimes = []

    for n in nvals:
        print("Working on n:", n)
        
        mylist = list(range(n))

        sstime = 0
        mstime = 0
        numTests = 1000
        for i in range(numTests):
            random.shuffle(mylist)

            shuffled1 = mylist[:]
            shuffled2 = mylist[:]
        
            t = time.time()

            selectionSort(shuffled1)

            sstime += (time.time() - t)
            t = time.time()

            mergeSort(shuffled2)

            mstime += (time.time() - t)

        selectionTimes.append(sstime / numTests * 1000)
        mergeTimes.append(mstime / numTests * 1000)

    plt.figure()
    plt.plot(nvals, selectionTimes, label="Selection Sort Time (ms)")
    plt.plot(nvals, mergeTimes, label="Merge Sort Time (ms)")
    plt.xlabel("Number of elements in the list")
    plt.ylabel("Sort time (ms)")
    plt.legend()
    plt.show()

if __name__ == "__main__":
    timeSorts()