## Fonctions pour les piles
def estvide(p):
    return(p==[])

def newpile():
    return([])

def depile(p):
    return(p.pop())

def empile(x,p):
    p.append(x)

def sommet(p):
    return(p[-1])
##
import matplotlib.pyplot as plt
from random import randint
L1 = [2*i+1 for i in range(10)]
L2 = [2*i for i in range(10)]

def listalea(a,b,n):
    return([randint(a,b) for i in range(n)])

def fusion1(L1,L2):
    if L1 == [] or L2 == []:
        return(L1+L2)
    if L1[0] <= L2[0]:
        L = [L1[0]]
        L = L + fusion1(L1[1:len(L1)],L2)
    else :
        L = [L2[0]]
        L = L + fusion1(L1,L2[1:len(L2)])
    return(L)


L = listalea(0,20,20)


def trifusion1(L):
    n = len(L)
    if n <=1:
        return L
    else :
        return(fusion1(trifusion1(L[0:n//2]),trifusion1(L[n//2:n])))




##from time import clock
##plt.figure('Complexite')
##T = []
##for n in range(2,900):
##    L = listalea(0,n,n)
##    t1 = clock()
##    trifusion1(L)
##    t2 = clock()
##    T.append(t2-t1)
##
##plt.plot([T[i]/(i+2) for i in range(2,len(T)-2)])
##plt.show()

# Lineaire

## Tri Rapide :


def partage1(L,p):
    L1 = []
    L2 = []
    for i in L:
        if i < p :
            L1.append(i)
        else :
            L2.append(i)
    return(L1,L2)

def estrie(L):
    if len(L) <= 1:
        return True
    else :
        if L[0]<=L[-1]:
            return estrie(L[1:])
    return False

def trirapide1(L):
    if len(L) <=1 :
        return L
    else :
        return(trirapide1(partage1(L[1:],L[0])[0]) +[L[0]] + trirapide1(partage1(L[1:],L[0])[1]))


##from time import clock
##plt.figure('Complexite')
##T = [[],[]]
##for n in range(2,900):
##    L = listalea(0,n,n)
##    t1 = clock()
##    trifusion1(L)
##    t2 = clock()
##    T[0].append(t2-t1)
##    t1 = clock()
##    trirapide1(L)
##    t2 = clock()
##    T[1].append(t2-t1)
##
##plt.plot([T[0][i]/(i+2) for i in range(2,len(T[0])-2)])
##plt.plot([T[1][i]/(i+2) for i in range(2,len(T[0])-2)], label = 'Tri Rapide')
##plt.legend()
##plt.show()











##plt.figure('trifusion1')
##plt.plot(L)
##plt.plot(trifusion1(L))
##plt.show()