import sys
import time
import random
import matplotlib.pyplot as plt


array = []
n = input()

BestCase = []
BestTime = [[], [], [], [], [], []]

WorstCase = []
WorstTime = [[], [], [], [], [], []]

AveregeCase = []
AverageTime = [[], [], [], [], [], []]


def mergesort(array):
    mergesortidx(array, 0, len(array)-1)

def insertionSort(array, mid):
    for i in range(len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and key < array[j]:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = key
    return array

def mergesortidx(array, first, last):
    if first < last:
        mid = (first + last)//2
        if mid <= array:
            insertionSort(array, mid)
        else:
            mergesortidx(array, first, mid)
            mergesortidx(array, mid+1, last)
            merge(array, first, mid, last)

def merge(array, first, mid, last):
    l = array[first:mid + 1]
    r = array[mid+1:last + 1]
    l.append(sys.maxsize)
    r.append(sys.maxsize)
    i = j = 0

    for k in range(first, last + 1):
        if l[i] <= r[j]:
            array[k] = l[i]
            i += 1
        else:
            array[k] = r[j]
            j += 1

def ComputationTime(array):
    start = time.time()
    mergesortidx(array, 0, len(array) - 1)
    end = time.time()
    return end - start


fig, ax = plt.subplots(1)
fig2, ax2 = plt.subplots(1)
fig3, ax3 = plt.subplots(1)

for i in range(0, n):
    BestCase.append(i)
    BestTime[0].append(ComputationTime(BestCase))
    BestTime[1].append(ComputationTime(BestCase))
    BestTime[2].append(ComputationTime(BestCase))
    BestTime[3].append(ComputationTime(BestCase))
    BestTime[4].append(ComputationTime(BestCase))
    BestTime[5].append(ComputationTime(BestCase))

for i in range(0, n):
    WorstCase.append(n - (i + 1))
    WorstTime[0].append(ComputationTime(WorstCase))
    WorstTime[1].append(ComputationTime(WorstCase))
    WorstTime[2].append(ComputationTime(WorstCase))
    WorstTime[3].append(ComputationTime(WorstCase))
    WorstTime[4].append(ComputationTime(WorstCase))
    WorstTime[5].append(ComputationTime(WorstCase))

for i in range(0, n):
    AveregeCase.append(random.randint(0,1000))
    AverageTime[0].append(ComputationTime(AveregeCase))
    AverageTime[1].append(ComputationTime(AveregeCase))
    AverageTime[2].append(ComputationTime(AveregeCase))
    AverageTime[3].append(ComputationTime(AveregeCase))
    AverageTime[4].append(ComputationTime(AveregeCase))
    AverageTime[5].append(ComputationTime(AveregeCase))

ax.set_title('BestCase Time')
plt.xlabel('Sample n (n)')
plt.ylabel('Computation time (sec)')
ax.plot(range(0,n), BestTime[0], label = '' + str(int((n/10)*0)))
ax.plot(range(0,n), BestTime[1], label = '' + str(int((n/10)*1)))
ax.plot(range(0,n), BestTime[2], label = '' + str(int((n/10)*2)))
ax.plot(range(0,n), BestTime[3], label = '' + str(int((n/10)*3)))
ax.plot(range(0,n), BestTime[4], label = '' + str(int((n/10)*4)))
ax.plot(range(0,n), BestTime[5], label = '' + str(int((n/10)*5)))
fig.show()

ax2.set_title('WorstCase Time')
ax2.plot(range(0,n), WorstTime[0], label = '' + str(int((n/10)*0)))
ax2.plot(range(0,n), WorstTime[1], label = '' + str(int((n/10)*1)))
ax2.plot(range(0,n), WorstTime[2], label = '' + str(int((n/10)*2)))
ax2.plot(range(0,n), WorstTime[3], label = '' + str(int((n/10)*3)))
ax2.plot(range(0,n), WorstTime[4], label = '' + str(int((n/10)*4)))
ax2.plot(range(0,n), WorstTime[5], label = '' + str(int((n/10)*5)))
fig2.show()

ax3.set_title('Average case')
ax3.plot(range(0,n), AverageTime[0], label = '' + str(int((n/10)*0)))
ax3.plot(range(0,n), AverageTime[1], label = '' + str(int((n/10)*1)))
ax3.plot(range(0,n), AverageTime[2], label = '' + str(int((n/10)*2)))
ax3.plot(range(0,n), AverageTime[3], label = '' + str(int((n/10)*3)))
ax3.plot(range(0,n), AverageTime[4], label = '' + str(int((n/10)*4)))
ax3.plot(range(0,n), AverageTime[5], label = '' + str(int((n/10)*5)))
fig3.show()

fig.savefig("BestCase.png", bbox_inches='tight')
fig3.savefig("AverageCase.png", bbox_inches='tight')
fig2.savefig("WorstCase.png", bbox_inches='tight')