#!/usr/bin/env python
# coding: utf-8

# In[227]:


#Luis Gonzalez 21/01/2019 Code Session 2.1 - Mergesort and recurrences
import random
# Here I imported the relevant python dependencies that I used for this algorithm. I only imported random from the standard Python Libarary in this case


# In[228]:


#I first declar the function "merge" and pass the values of start,middle,length rather than p,q,r respectivly as the readings mentioned. I did this change becuase it was easier for me to conceptualize the code in this form rather than with the way the book had it written
def Merge(A,start,middle,length):
    global count
    #I created a global variable this time rather than appending the counter in list form. This enables me to retrive the counter in other places in the code
    n1 = int(middle-start+1)
    #I created the length of the first list by subratinc the start of the list minus the middle
    count =count+1
    #After each line code I increase the counter by one
    n2 = int(length-middle)
    #I then created the length of the second list by subtrating the total lenght of the list minus the middle
    count =count+1
    Left = [0]*(n1+1)
    #Here I assigne the value of the left list to the number I obtained previously
    count =count+1
    Right = [0]*(n2+1)
    # I do the same things as in the left assignation
    count =count+1
    for i in range(0,n1):
        count =count+1
        Left[i] = A[start+i]
        #Here I basically assign the values of the array to the new Left list
        count =count+1
    for j in range(0,n2):
        count =count+1
        Right[j] = A[middle+1+j]
        #Here I  assign the values of the array to the new Right list
        count =count+1
    Left[n1] = 9999999
    #I then make the last number of the list extreamly large in order to identify when the code should stop
    count =count+1
    Right[n2] = 9999999
    #I do the same as the previous step
    count =count+1
    i = 0
    count =count+1
    j = 0
     #Here I made the counters 0 again in order to use them in he next loop
    count =count+1
    for k in range(int(start),int(length)+1):
        count =count+1
        if Left[i]<= Right[j]:
            #Here I compare the values of each lists and "append" the smalles value to the original list
            count =count+1
            A[k] = Left[i]
            count =count+1
            i=i+1
            #Increase i by 1
            count =count+1
        else:
            count =count+1
            A[k] = Right[j]
            count =count+1
            j=j+1
            #Increase j by 1
            count =count+1
    return count
# I finally returned the value of count in order to use it outside of the function


# In[229]:


#I created a new function called MergeSort
def MergeSort(A,start, length):
    global count
    # I once again assigne the value of count as a global variable
    count =count+1
    if start < length:
        #This part checks that the array is not a single sigit as that would make this if statement false and then return the count only
        count =count+1
        middle = (int(start+length)//2)
        #I assigned the value of middle of the array simply dividing the length of the array plus the start.
        #I used the "//" division rather than "/" because in Python 3, this bring a float and I needed an integer
        count =count+1
        MergeSort(A,start,middle)
        #I call the function on the new list to further divide it
        count =count+1
        MergeSort(A,middle+1,length)
        #I call the function on the other new list to further divide it
        count =count+1
        Merge(A,start,middle,length)
        #I finally start merging once I have the start middle and length
        count =count+1
    return count


# In[230]:


count = 0
#I initialize the counter
array = []
# I create an empty array
count =count+1
for x in range(6):
    #I made a simply loop to append 6 randomly generated numbers
    count =count+1
    array.append(random.randint(1,99))
    count =count+1

print("Initial Array of 6 numbers")
print(array)
#I print the initial array
MergeSort(array,0, len(array)-1)
# I call the function on the array and relevant values
count =count+1
print("Sorted Array of six numbers")
print(array)
print("Total count")
print(count)
# Finally I printed the values generated at the end.


# In[242]:


import matplotlib.pyplot as plt
#I first Imported the relevant libarary to use which in this case is matplotlib

# Here I called the function with 5 different array lengths in order to create a graph of the relationship between numbers in an array and time steps.
array1 = []
array2 = []
array3 = []
array4 = []
array5 = []

# I looped and appended random values to the lists while looping 2x more numbers in each list

for x in range(4):
    count =count+1
    array1.append(random.randint(1,99))
    count =count+1

for x in range(8):
    count =count+1
    array2.append(random.randint(1,99))
    count =count+1

for x in range(16):
    count =count+1
    array3.append(random.randint(1,99))
    count =count+1

for x in range(32):
    count =count+1
    array4.append(random.randint(1,99))
    count =count+1

for x in range(64):
    count =count+1
    array5.append(random.randint(1,99))
    count =count+1

# I then initialized the counting for each particulat algorithm given n amount of numbers

count=0
count1=0
count2=0
count3=0
count4=0
count5=0
count= 0

# I call the fucntion with the specific array and print the counter for each sort
MergeSort(array1,0, len(array1)-1)
count1 = count
print(count1)
MergeSort(array2,0, len(array2)-1)
count2 = count
print(count2)
MergeSort(array3,0, len(array3)-1)
count3 = count
print(count3)
MergeSort(array4,0, len(array4)-1)
count4 = count
print(count4)
MergeSort(array5,0, len(array5)-1)
count5 = count
print(count5)

# I then used the values from the steps and plotted them on this graph based on the number of numbers used on the x

y_vals = [count1,count2,count3,count4,count5,count6]
x_vals = [4,8,16,32,64,128]
plt.scatter(y_vals,x_vals)
plt.title("Merge Sort Visualized")
plt.xlabel("N integers in a list")
plt.ylabel("yNumber of steps counted")
plt.show()


# In[ ]: