Illustration.

Vous pouvez observer ci-dessous le tri par fusion d'une liste en action.

Cliquez sur le bouton "Manuel" pour dérouler les étapes à votre rythme et comprendre ces étapes d'exécution.

Le bouton "Automate" enchaîne les étapes avec un intervalle de temps d'environ 3 secondes entre deux étapes (vous pouvez réduire ce temps en cliquant sur la petite flèche du formulaire contenant le nombre 3000).

Pour accélérer l'automate, régler ici le temps (en ms) qui sépare deux étapes :

formulation de l'algorithme.

Formulez, en français, l'algorithme de tri par fusion d'une liste.

une formulation

Entrée	une liste L d'éléments comparables.
Initialisation	lg = 1
Traitement	On fusionne, deux par deux, les sous-listes consécutives de L de taille lg : L1 et L2 -- L3 et L4 -- L5 et L6 -- ... (il est possible que la dernière liste n'ait pas la taille lg, ce n'est pas important). lg=lg*2 On reprend au point 1 jusqu'à ce que lg > taille initiale de L.
Sortie	L, triée.

programmer.

Écrire une fonction python de tri d'une liste (de nombres par exemple) par fusion.

On utilisera la fonction de l'exercice "doubler la taille des segments triés" de la page concernant le principe de fusion.

un code possible
avec traces des étapes


from random import randint

def fusion(L, p, q, r) :
	L3 = []
	i, j = p, q
	
	# boucle posant en queue de L3
	# les min des têtes des sous-listes L1, L2
	while i < q and j < r :
		if L[i] < L[j] :
			L3.append(L[i])
			i += 1
		else :
			L3.append(L[j])
			j += 1
			
	# une sous-liste étant vidée
	# on colle tout le contenu 
	# non encore traité de l'autre sous-liste
	# en queue de L3 
	if i == q : 
		for k in range(j, r) :
			L3.append(L[k])
	else :
		for k in range(i, q) :
			L3.append(L[k])
			
	# on copie dans la liste L initiale
	# la fusion obtenue :
	for k in range(p, r) :
		L[k] = L3[k-p]

def doublekTri(L,k) :
	p = 0
	q = min(p+k, len(L))
	r = min( q+k, len(L)) 
	while p < len(L)-1 :
		fusion(L, p, q, r)
		p = r
		q = min(p+k, len(L))
		r = min( q+k, len(L)) 


def trifusion(L) :
	k = 1
	while k < len(L) :
		doublekTri(L,k)
		k *= 2

# tirage au hasard d'une liste d'entiers de taille n
n = 10 
L = [ randint(1, 3*n) for j in range(n) ]
print(L)
trifusion(L)
print(L)


from random import randint

def fusion(L, p, q, r) :
	L3 = []
	i, j = p, q

	# boucle posant en queue de L3
	# les min des têtes des sous-listes L1, L2
	while i < q and j < r :
		if L[i] < L[j] :
			L3.append(L[i])
			i += 1
		else :
			L3.append(L[j])
			j += 1

	# une sous-liste étant vidée
	# on colle tout le contenu
	# non encore traité de l'autre sous-liste
	# en queue de L3
	if i == q :
		for k in range(j, r) :
			L3.append(L[k])
	else :
		for k in range(i, q) :
			L3.append(L[k])

	# on copie dans la liste L initiale
	# la fusion obtenue :
	for k in range(p, r) :
		L[k] = L3[k-p]

def doublekTri(L,k) :
	p = 0
	q = min(p+k, len(L))
	r = min( q+k, len(L))
	while p < len(L)-1 :
		fusion(L, p, q, r)
		p = r
		q = min(p+k, len(L))
		r = min( q+k, len(L))
	print("Fusion des segments consécutifs de longueur {} : ".format(k))
	for i in range(len(L)) :
		if i % (2*k) == 2*k-1 :
			print(L[i], end='  | ')
		else : print(L[i], end=' ')
	print()
		


def trifusion(L) :
	k = 1
	while k < len(L) :
		doublekTri(L,k)
		k *= 2

# tirage au hasard d'une liste d'entiers de taille n
n = 10
L = [ randint(1, 3*n) for j in range(n) ]
print("Liste avant tri : ", L)
print()
print("Etapes du tri : ")
trifusion(L)
print("\nAprès le tri : ", L)

On obtient par exemple :

Liste avant tri :  [6, 5, 15, 28, 3, 10, 2, 23, 1, 28]

Etapes du tri : 
Fusion des segments consécutifs de longueur 1 : 
5 6  | 15 28  | 3 10  | 2 23  | 1 28  | 
Fusion des segments consécutifs de longueur 2 : 
5 6 15 28  | 2 3 10 23  | 1 28 
Fusion des segments consécutifs de longueur 4 : 
2 3 5 6 10 15 23 28  | 1 28 
Fusion des segments consécutifs de longueur 8 : 
1 2 3 5 6 10 15 23 28 28 

Après le tri :  [1, 2, 3, 5, 6, 10, 15, 23, 28, 28]

version récursive.

Proposer une version récursive du tri par fusion.

le principe
un code possible
tri de la liste initiale

Une liste de longueur au plus 1 est triée.
Dans les autres cas, le tri est obtenu par fusion de la première moitié de liste triée et de la seconde moitié de liste triée.


from random import randint

def fusion(L1, L2) :
	L3 = []
	
	# boucle posant en queue de L3
	# les min des têtes des sous-listes L1, L2
	while L1 and L2 :
		if L1[0] < L2[0] : L3.append(L1.pop(0))
		else : L3.append(L2.pop(0))
			
	# une sous-liste étant vidée
	# on colle tout le contenu de l'autre
	# en queue de L3 
	L3 = L3+L1+L2
	
	return L3
			

def trifusion(L) :
	n = len(L)
	if n <= 1 : return L
	else : return fusion( trifusion(L[:n//2]), trifusion(L[n//2 : ] ) )

# tirage au hasard d'une liste d'entiers de taille n
n=10 
L = [ randint(1, 3*n) for j in range(n) ]
print(L)
L=trifusion(L)
print(L)

La solution précédente produit une nouvelle liste triée et a de plus le défaut de produire de nouvelles listes à chaque nouvel appel de la fonction récursive, d'où un coût en mémoire important (chaque liste créée dans les appels est nécessairement maintenue en mémoire pour les remontées).

Dans la version récursive ci-dessous, on trie la liste L elle-même, les seules listes intermédiaires créées sont celles qui sont créées lors des exécutions de la fonction fusion (elles disparaissent à chaque sortie de la fonction fusion)


from random import randint

def fusion(L, p, q, r) :
	"""
	fusion des segments triés :
	segment1 = [L[p],L[p+1],L[p+2],...,L[q]]
	segment2 = [L[q+1],L[q+2],L[q+3],...,L[r]]
	"""
	L3 = []
	i, j = p, q+1

	# boucle posant en queue de L3
	# les min des têtes des segments :
	while i <= q and j <= r :
		if L[i] < L[j] :
			L3.append(L[i])
			i += 1
		else :
			L3.append(L[j])
			j += 1

	# une sous-liste étant vidée
	# on colle tout le contenu
	# non encore traité de l'autre sous-liste
	# en queue de L3
	if i == q+1 :
		for k in range(j, r+1) :
			L3.append(L[k])
	else :
		for k in range(i, q+1) :
			L3.append(L[k])

	# on copie dans la liste L initiale
	# la fusion obtenue :
	for k in range(p, r+1) :
		L[k] = L3[k-p]



def tri_fusion(L, deb, fin):
	if deb < fin :
		milieu = (deb+fin)//2
		tri_fusion(L, deb, milieu)
		tri_fusion(L, milieu+1, fin)
		fusion(L, deb, milieu, fin)

# tirage au hasard d'une liste d'entiers de taille n
n = 10
L = [ randint(1, 3*n) for j in range(n) ]
print(L)
tri_fusion(L, 0, len(L)-1)
print(L)