Tri des listes de données est un problème qui a vexé les programmeurs depuis le début de la programmation informatique . Tri toute liste de données peut finir comme une tâche de mémoire et beaucoup de temps. Pour cette raison , les différentes méthodes de tri ont été inventés pour minimiser le défi et de l'effort de tri . Une méthode consiste à fusionner le tri . Elle subdivise une liste récursive en éléments singuliers et recombine la liste sous forme triée. N'importe quel langage de programmation qui supporte la récursivité , tels que Python, peut mettre en place un tri par fusion . Choses que vous devez
interpréteur Python avec l'environnement de développement interactif
Voir Plus Instructions
1

définir la fonction " mergesort " . Cette fonction de base s'appelle récursivement , diviser la taille de la liste de moitié à chaque appel . Une fois la fonction mergesort frappe une liste avec un élément, la récursivité s'arrête et le rendement de l'élément. Comme les déroule de récurrence mergesort , chaque petite liste est fusionné ensemble dans l'ordre. Cet exemple affiche une fonction de mergesort de base qui prend une liste en argument :

>>> def mergesort ( li ) :

. . . if len ( li ) < 2:

. . . retourner li

. . . mid = len ( li ) /2

. . . premier = mergesort ( li [ : mi ] )

. . . last = mergesort ( li [ mi : ] )

. . . retourner fusionner ( first, last)
2

Mettre en place la méthode de fusion. Cette fonction servira de la méthode de tri : elle renvoie une liste triée des éléments. La méthode de fusion prend deux listes déjà triées. Il définit ensuite une liste interne " triés " qui représentera les listes d'arguments triés combinés. La méthode de fusion accomplit cette mission en prenant le plus petit élément et en l'insérant dans une nouvelle liste " classifiées " . Une fois que l'une des listes extrémités , l'autre liste est inséré dans son intégralité

>>> def fusion ( x , y) : .

. . . sorted = []
3

fusionner les listes dans la méthode de fusion. La boucle "while" dans l'exemple compare chaque élément de la liste en question , en prenant le plus petit élément et en l'insérant dans une nouvelle liste " classifiées " . Une fois que l'une des listes se termine, l'autre liste est insérée dans son intégralité, et la nouvelle liste triée est renvoyée:

. . . i , j = 0, 0

. . . tandis que i < len ( x ) et j < len ( y) :

. . . si x [ i ] < = y [j] :

. . . sorted.append ( x [i])

. . . i + = 1

. . . autre :

. . . sorted.append ( y [ j])

. . . j + = 1

. . . triés + = x [ I: ]

. . . triés + = y [: j]

. . . retourner triés