### algoFusion - 21/04/2014 ###


## pileA != pileB != pileC != pileA
def fusionne(pileA, nbElementsA, pileB, nbElementsB, pileC, ordreCroissant):
   
    while nbElementsA > 0:
        depile(pileA)
        continuer = True
        while nbElementsB > 0 and continuer:
            empile(pileB)
            if plus_grand(pileB) != ordreCroissant :
                depile(pileB)
                continuer = False
            else :
                depile(pileB)
                deplace_sommet(pileB, pileC)
                nbElementsB -= 1
        empile(pileC)
        nbElementsA -= 1
        
    while nbElementsB > 0:
        depile(pileB)
        empile(pileC)
        nbElementsB -= 1
   

def deplaceEtTrie(pileATriee, nbElements, pileCible, ordreCroissant):
    
    pileIntermediaire1 = 1
    pileIntermediaire2 = 1
    while pileIntermediaire1 == pileCible or pileIntermediaire1 == pileATriee:
        pileIntermediaire1 += 1
    while pileIntermediaire2 == pileCible or pileIntermediaire2 == pileIntermediaire1:
        pileIntermediaire2 += 1

    if nbElements == 1 and pileATriee != pileCible:
        depile(pileATriee)
        empile(pileCible)
    
    if nbElements == 2:
        if pileATriee == pileCible:
            if plus_grand(pileATriee) != ordreCroissant:
                depile(pileATriee)
                deplace_sommet(pileATriee, pileIntermediaire1)
                empile(pileATriee)
                depile(pileIntermediaire1)
                empile(pileATriee)
        else :
            if plus_grand(pileATriee) != ordreCroissant:
                depile(pileATriee)
                empile(pileCible)
                depile(pileATriee)
                empile(pileCible)
            else :
                depile(pileATriee)
                deplace_sommet(pileATriee, pileCible)
                empile(pileCible)
    
    if nbElements == 3:
        if pileATriee == pileCible:
            if plus_grand(pileATriee) != ordreCroissant:
                depile(pileATriee)
                deplace_sommet(pileATriee, pileIntermediaire1)
                empile(pileATriee)
                if plus_grand(pileATriee) != ordreCroissant:
                    depile(pileATriee)
                    deplace_sommet(pileATriee, pileIntermediaire1)
                    empile(pileATriee)
                    if plus_grand(pileIntermediaire1) != ordreCroissant:
                        depile(pileIntermediaire1)
                        empile(pileATriee)
                        depile(pileIntermediaire1)
                        empile(pileATriee)
                    else :
                        depile(pileIntermediaire1)
                        deplace_sommet(pileIntermediaire1, pileATriee)
                        empile(pileATriee)
                else:
                    depile(pileIntermediaire1)
                    empile(pileATriee)
            else :
                depile(pileATriee)
                if plus_grand(pileATriee) != ordreCroissant:
                    empile(pileIntermediaire1)
                    depile(pileATriee)
                    deplace_sommet(pileATriee, pileIntermediaire1)
                    empile(pileATriee)
                    if plus_grand(pileIntermediaire1) != ordreCroissant:
                        depile(pileIntermediaire1)
                        empile(pileATriee)
                        depile(pileIntermediaire1)
                        empile(pileATriee)
                    else :
                        depile(pileIntermediaire1)
                        deplace_sommet(pileIntermediaire1, pileATriee)
                        empile(pileATriee)
                else :
                    empile(pileATriee)
        else :
            if plus_grand(pileATriee) != ordreCroissant:
                depile(pileATriee)
                if plus_grand(pileATriee) != ordreCroissant:
                    empile(pileCible)
                    depile(pileATriee)
                    empile(pileCible)
                    depile(pileATriee)
                    empile(pileCible)
                else :
                    deplace_sommet(pileATriee, pileIntermediaire1)
                    empile(pileATriee)
                    if plus_grand(pileATriee) != ordreCroissant:
                        depile(pileATriee)
                        empile(pileCible)
                        depile(pileATriee)
                        empile(pileCible)
                    else :
                        depile(pileATriee)
                        deplace_sommet(pileATriee, pileCible)
                        empile(pileCible)
                    depile(pileIntermediaire1)
                    empile(pileCible)
            else :
                depile(pileATriee)
                if plus_grand(pileATriee) != ordreCroissant:
                    deplace_sommet(pileATriee, pileCible)
                    empile(pileATriee)
                    if plus_grand(pileATriee) != ordreCroissant:
                        depile(pileATriee)
                        empile(pileCible)
                        depile(pileATriee)
                        empile(pileCible)
                    else :
                        depile(pileATriee)
                        deplace_sommet(pileATriee, pileCible)
                        empile(pileCible)
                else :
                    empile(pileIntermediaire1)
                    depile(pileATriee)
                    deplace_sommet(pileATriee, pileCible)
                    empile(pileCible)
                    depile(pileIntermediaire1)
                    empile(pileCible)
    
    if nbElements > 3:
        # on sépare en deux piles triées.
        deplaceEtTrie(pileATriee, nbElements // 2, pileIntermediaire1, not ordreCroissant)
        deplaceEtTrie(pileATriee, nbElements - nbElements // 2, pileIntermediaire2, not ordreCroissant)
        fusionne(pileIntermediaire1, nbElements // 2, pileIntermediaire2, nbElements - nbElements // 2, pileCible, ordreCroissant)
   

def algoFusion():

    #print (""**** LANCEMENT ****"")

    #affiche_piles()

    #print (""debut de l'algo"")

    nombreTotalElements = nombre_element(1)

    if nombreTotalElements == 2:
        if not plus_grand(1):
            echange_sommet(1)

    if nombreTotalElements == 3:
        if not plus_grand(1):
            echange_sommet(1)
        depile(1)
        plop = False
        if not plus_grand(1):
            echange_sommet(1)
            plop = True
        empile(1)
        if plop:
            if not plus_grand(1):
                echange_sommet(1)

    if nombreTotalElements > 3:

        cree_pile()
        cree_pile()

        deplaceEtTrie(1, nombreTotalElements, 1, True)

                
    #print (""fin de l'algo"")
    
    #affiche_piles()
    
    return


### programme principal ###
affiche_piles()
algoFusion()
affiche_piles()