# tri par fusion
# type:ignore
def fusion(L1,L2,m1,m2):
    L=[]
    j1=0
    j2=0
    while (j1<m1) and (j2<m2):
        if L1[j1]<L2[j2]:
            L+=[L1[j1]]
            j1+=1
        else:
            L+=[L2[j2]]
            j2+=1
    if j1==m1:
        L+=L2[j2:m2]
    else:
        L+=L1[j1:m1]
    return L
    
def tri_par_fusion(L,n):
    if n==1:
        return L
    m=n//2
    L1=tri_par_fusion(L[0:m],m)
    L2=tri_par_fusion(L[m:n],n-m)
    L=fusion(L1,L2,m,n-m)
    return L


# tri par insertion
def permuter(L,j,k):
    temp=L[j]
    L[j]=L[k]
    L[k]=temp
    return L

def inserer(L,i):
    j=i
    while j>0 and L[j]<L[j-1]:
        L=permuter(L,j,j-1)
        j=j-1
    return L

def tri_par_insertion(L,n):
    for i in range(1,n):
        if L[i]<L[i-1]:
            L=inserer(L,i)
    return L


from random import *
from time import *
n=int(input("Taille de la liste:"))
L0=sample(range(-n,n+1),n)
if n<=100:
    print("Liste non triée:",L0)
t0=time()
L=tri_par_fusion(L0,n)
t1=time()-t0
if n<=100:
    print("Liste triée par fusion:",L)
t0=time()
L=tri_par_insertion(L0,n)
t2=time()-t0
if n<=100:
    print("Liste triée par insertion:",L)
print("Temps par fusion:",t1)
print("Temps par insertion:",t2)