from math import floor
from matplotlib import pyplot as plt
import random

def merge_sort(lista):
    zliczanie = 0
    if len(lista)<=1:
        return zliczanie

    lewa = lista[:len(lista)//2]
    prawa = lista[len(lista)//2:]

    merge_sort(lewa)
    merge_sort(prawa)
    tmp, zliczanie = merge(lewa, prawa)
    lista.clear()
    lista.extend(tmp)
    return zliczanie

def merge(lewa, prawa):
    zliczanie = 0
    wynik = []
    while lewa and prawa:
        zliczanie += 1
        if lewa[0] <= prawa[0]:
            zliczanie += 1
            wynik.append(lewa.pop(0))
        else:
            zliczanie += 1
            wynik.append(prawa.pop(0))
    while lewa:
        zliczanie += 1
        wynik.append(lewa.pop(0))
    while prawa:
        zliczanie += 1
        wynik.append(prawa.pop(0))
    return wynik, zliczanie

def start():
    wyniki= []
    i = 1
    for i in range(1000):
        lista = list(range(i))
        random.shuffle(lista)
        wyniki.append(merge_sort(lista))
    return wyniki

wyniki = start()
print(wyniki)
plt.plot(wyniki)
plt.show()