# Créé par Devouges_2, le 17/01/2014 en Python 3.2
from math import *
def recherche(x,tab,i,j):
    # recherche est une fonction récursive qui utilise la dichotomie pour rechercher un élément x dans un tableau trié
    #entre les indices i et j compris
    # l'idée est simple: on compare x à l'élément "central" de tab et selon qu'il est plus petit ou plus grand on recherche
    # sur une de 2 "moitiés" de tab
    # La terminaison des appels récursifs se fait quand il n'y a plus qu'un seul élément (i=j)
    #et dans ce cas soit x est égal à cet élément soit différent
    if i==j:
        if tab[i]==x:
            return i
        else:
            return -1
    else:
        if x<=tab[floor((i+j)/2)]:
            return recherche(x,tab,i,floor((i+j)/2))
        else:
            return recherche(x,tab,floor((i+j)/2+1),j)
def max(tab): # retourne le plus grand élément de tab + 1
              # ainsi max est strictement plus grand que tous le éléments de tab
    x=tab[0]
    for i in range(1,len(tab)):
        if tab[i]>x:
            x=tab[i]
    return x+1



def fusion(tab,i,j,k):# le tableau tab est trié de l'indice i à l'indce j compris et de l'indice j+1 à l'indice k compris
                      # fusion fuionne le 2 parties triées en une seule triée
    tab1=list(range(j-i+2)) # on crée un tableau qui contient les éléments de tab de i à j compris plus un supplémentaire max(tab)
    tab2=list(range(k-j+1)) # même chose de j+1 à k compris
    for u in range(j-i+1):
        tab1[u]=tab[u+i]
    tab1[j-i+1]=max(tab)
    for u in range(k-j):
        tab2[u]=tab[u+j+1]
    tab2[k-j]=max(tab)
    x=0 # x est l'indice courant de tab1 et y l'indice courant de tab2
    y=0
    # on remplace tous les éléments de tab par ceux de tab1 ou tab2 selon lequel est le plus petit
    # quand un élément d'un tableau est utilisé on incrémente l'indice courant correspondant
    # max(tab) joue le rôle de sentinelle ou de butoir car l'indice courant ne pourra pas aller au delà
    #sans cette astuce , l'indice courant peut dépasser la taille de tab1 ou de tab2 et donc générer une erreur
    for l in range(k-i+1):
        if tab1[x]<=tab2[y]:
            tab[l+i]=tab1[x]
            x=x+1
        else:
           tab[l+i]=tab2[y]
           y=y+1

def trifusion(tab,i,k):
    # trifusion trie les éléments de tab des indices i à k compris
    # On sépare les éléments concernés en "2" parties (méthode dichotomique) qui sont triées par trifusion (appel récurrif)
    # puis on fusionne le 2 parties une fois triées
    if i<k:
        j=floor((i+k)/2)
        trifusion(tab,i,j)
        trifusion(tab,j+1,k)
        fusion(tab,i,j,k)
   # trifuion se termine quand il n'y a plus qu'un seul élément(i=k)
   # auquel cas il n' y a rien à trier donc rien à faire

tab=[2,12,6,8,0,1,5]
trifusion(tab,0,6) # utilisation de trifusion sur tous les éléments du tableau tab (indices 0 à 6 compris)
print(tab) # affiche  tab pour tester trifusion