import matplotlib.pyplot as plt
from timeit import timeit
from random import randint
import itertools as it

#merge is intercalation . sort tow vectors in crescent order,
#intercale and put them in crescent order too

# The interleave function consists essentially of moving elements of the vector v from one place to another (first from v to w and then from w to v).
# The function executes 2n of these moves, where n is the size of the vector v [p..r-1].
# The time it consumes is proportional to the number of movements.
# Therefore, the time consumption of the function is proportional to n. Thus, the algorithm is linear.

def mergeSort(x):
    result = []
    # if len(vector is smaller than 2, the vector is arranged)
    if len(x) < 2:
        return x
    # divide your vector in the middle and call recursively the function
    #the function is called until all the vector is ordered
    mid = int(len(x)/2)
    y = mergeSort(x[:mid])
    z = mergeSort(x[mid:])
    while (len(y) > 0) or (len(z) > 0):
        if len(y) > 0 and len(z) > 0:
            if y[0] > z[0]:
                result.append(z[0])
                z.pop(0)
            else:
                result.append(y[0])
                y.pop(0)
        elif len(z) > 0:
            for i in z:
                result.append(i)
                z.pop(0)
        else:
            for i in y:
                result.append(i)
                y.pop(0)
    return result

#generate unSorted array with gave lenght
def listGenerator(lenList):
    generated = []
    for i in range(lenList):
        while len(generated) != lenList:
            n = randint(1,1*lenList)
            if n not in generated: generated.append(n)
    return generated

def drawGraph(listQt,medium,best,worst,xl = "Elementos", yl = "Tempo"):
    fig = plt.figure(figsize=(10, 8))
    ax = fig.add_subplot(111)
    ax.plot(listQt,medium, label = "Caso Medio")
    ax.plot(listQt,best, label = "Melhor Caso")
    ax.plot(listQt,worst, label="Pior Caso")
    ax.legend(bbox_to_anchor=(1, 1),bbox_transform=plt.gcf().transFigure)
    plt.ylabel(yl)
    plt.xlabel(xl)
    plt.show()
    fig.savefig('mergeSort.png')

#lenghts to diferent arrays
length = [10000,20000,30000,40000,50000]

#array to store the necessary time to sort each array
mediumTimes = []
bestTimes = []
worstTimes = []

for i in length:
	mediumList = listGenerator(i)
	bestList = sorted(mediumList)
	worstList = sorted(bestList, reverse=True)

	mediumTimes.append(timeit("mergeSort({})".format(mediumList),setup="from __main__ import mergeSort",number=1))
	bestTimes.append(timeit("mergeSort({})".format(bestList),setup="from __main__ import mergeSort",number=1))
	worstTimes.append(timeit("mergeSort({})".format(worstList),setup="from __main__ import mergeSort",number=1))

drawGraph(length, mediumTimes, bestTimes, worstTimes)

# Verify the worst case
worstCaseExperience = list(it.permutations([1,2,3,4,5,6],6))

# permutimes and worstcase will have the same len, so the index is equivalent each other
permuTimes = []
swaps = []

for permutation in worstCaseExperience:
    listToSort = list(permutation)
    permuTimes.append(timeit("mergeSort({})".format(listToSort),setup="from __main__ import mergeSort",number=1))
    swaps.append(mergeSort(listToSort))

smallerTime = min(permuTimes)
greaterTime = max(permuTimes)

smallerTimeIndex = permuTimes.index(smallerTime)
greaterTimeIndex = permuTimes.index(greaterTime)

# worst case list
print("May be the worst: {}".format(worstCaseExperience[smallerTimeIndex]))
print("May be the best: {}".format(worstCaseExperience[greaterTimeIndex]))
print(swaps)