Merge Sort (Tri par fusion)
Le tri par fusion (Merge sort) est l’un des algorithmes de tri les plus rapides. De nombreuses applications utilisent une variante de Merge sort en production. Jusqu’à présent, nous avons abordé des algorithmes dont la complexité était quadratique, , comme Bubble sort (tri à bulles) ou Selection sort (tri par sélection). Merge sort est nettement plus rapide que ces algorithmes quadratiques et s’exécute en .
Merge sort est un algorithme de division-et-conquête (divide-and-conquer) qui trie récursivement des parties d’un tableau pour ensuite les fusionner. Le cœur de l’algorithme est la méthode efficace pour fusionner deux tableaux déjà triés en un seul tableau trié. Pendant son exécution, l’algorithme sépare le tableau en deux parties, trie récursivement la première, puis trie récursivement la seconde, et enfin fusionne ces deux tableaux triés pour n’en former plus qu’un :
def merge(a, b):
i, j, res = 0, 0, [] # Indices pour a et b, ainsi que le tableau résultant
while i < len(a) or j < len(b): # Tant qu'il reste des éléments
ai = a[i] if i < len(a) else float('inf')
bj = b[j] if j < len(b) else float('inf')
if ai < bj: # Si a[i] < b[j] => prendre a[i]
res.append(ai) # Ajouter a[i] au résultat
i += 1 # Passer à l'élément suivant
else: # Si a[i] >= b[j] => prendre b[j]
res.append(bj) # Ajouter b[j] au résultat
j += 1 # Passer à l'élément suivant
return res
def merge_sort(a):
if len(a) <= 1: # Rien à trier
return a # Retourner le tableau initial
l = merge_sort(a[: len(a) // 2]) # Trier la partie gauche
r = merge_sort(a[len(a) // 2:]) # Trier la partie droite
return merge(l, r)À chaque étape, l’algorithme prend un tableau, le divise en deux parties, trie chacune d’elles séparément, puis fusionne les tableaux obtenus pour créer un nouveau tableau. Notez que tous les algorithmes précédemment abordés modifiaient le tableau de départ en place (sans créer de nouveau tableau), tandis que le tri par fusion crée un nouveau tableau à chaque itération. Il est assez complexe de rendre le tri par fusion en place. Pouvez-vous expliquer pourquoi ?
Faisons une simulation de l’algorithme sur plusieurs tableaux :
[4, 1, -1, 0, 2, 8]
merge_sort([4, 1, -1, 0, 2, 8]):merge_sort([4, 1, -1])merge_sort([0, 2, 8])
merge_sort([4, 1, -1])merge_sort([4])→ return[4]merge_sort([1, -1])
merge_sort([0, 2, 8])merge_sort([1])→ return[1]merge_sort([-1])→ return[-1]
merge_sort([4, 1, -1]):
merge_sort([4])→ return[4]
merge_sort([1, -1])merge_sort([0])→ return[0]merge_sort([2, 8])
merge_sort([1, -1]):merge_sort([2])→ return[2]merge_sort([8])→ return[8]
merge_sort([1])→ return[1]
merge_sort([-1])→ return[-1]
- Back to
merge_sort([1, -1])→ return[-1, 1]
Challenge
Étant donné un tableau de
n entiers, il vous est demandé de les trier par ordre décroissant en utilisant l’algorithme Merge Sort.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 100 000).La ligne suivante contient
n entiers séparés par des espaces ( ≤ ≤ ) représentant le tableau de départ.Sortie
Le programme doit afficher
n entiers séparés par des espaces dans l’ordre décroissant.Exemples
Input | Output |
4
7 4 9 1 | 9 7 4 1 |
5
-4 8 2 -3 6 | 8 6 2 -3 -4 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 10 MB