[Jouer de la musique] 

DOUG LLOYD: OK, donc une fusion Trier est encore un autre algorithme que nous pouvons utiliser pour trier les éléments d'un tableau. Mais comme nous le verrons, il a un différence très fondamentale de la sélection sorte, bulle Trier, et le tri par insertion qui font qu'il est vraiment très intelligent. 

L'idée de base derrière fusion Trier est de trier les petits tableaux puis combiner ces réseaux ensemble, ou fusionner eux-- d'où le name-- dans l'ordre. La façon dont fusion ne sorte cela est en misant sur un outil appelé récurrence, ce qui est nous allons parler de bientôt, mais nous avons pas vraiment parlé encore. 

Voici l'idée de base derrière le tri par fusion. Trier la moitié gauche du tableau, en supposant que n est supérieur à 1. Et ce que je veux dire quand je dis en supposant que n est supérieur à 1 est, Je pense que nous pouvons convenir que si un tableau ne se compose que d'un seul élément, elle est triée. Nous ne devons pas réellement pour faire quoi que ce soit. Nous pouvons simplement déclarer à trier. Il est seulement un seul élément. 

Donc, le pseudo, encore une fois, est trier la moitié gauche de la matrice, ensuite trier la moitié droite du tableau, puis fusionner les deux moitiés ensemble. Maintenant, vous pourriez être déjà penser, il sorte de juste sonne comme vous mettez hors the-- vous n'êtes pas en train de faire quoi que ce soit. Vous dites trier la gauche la moitié, trier la moitié droite, mais vous ne dites pas moi comment vous le faites. 

Mais rappelez-vous que tant que un tableau est un seul élément, nous pouvons déclarer triée. Ensuite, nous pouvons simplement les combiner. Et qui est en fait le idée fondamentale derrière le tri par fusion, est de le décomposer afin que vos tableaux sont de la taille d'un. Et puis vous reconstruisez à partir de là. 

Tri par fusion est définitivement un algorithme compliqué. Et il est aussi un peu compliqué à visualiser. Donc, je l'espère, la visualisation que je avez ici va vous aider à suivre. Et je ferai de mon mieux pour raconter les choses et de passer par cela un peu plus lentement que les autres juste pour obtenir espérons votre tête autour des idées derrière tri par fusion. 

Donc, nous avons le même tableau que la autres vidéos de algorithme de tri si vous avez vu eux-- un ensemble de six éléments. Et notre code de pseudo ici est une sorte la moitié gauche, trier la moitié droite, fusionner les deux moitiés ensemble. Prenons donc cette brique très rouge foncé tableau et trier la moitié gauche de celui-ci. 

Donc, pour le moment, nous allons d'ignorer les trucs sur la droite. Il est là, mais nous sommes pas encore cette étape. Nous ne sommes pas à l'espèce moitié droite du tableau. Nous sommes à la gauche de tri moitié de la matrice. Et juste pour le plaisir d'être un peu plus clair, si je peux me référer à quelle étape nous sommes sur, Je vais passer la couleur de cet ensemble à l'orange. Maintenant, nous parlons toujours de la même la moitié gauche du tableau d'origine. Mais je suis en espérant que, en étant en mesure de reportez-vous aux couleurs de divers éléments, ça va faire un peu plus effacer ce qui se passe ici. 

OK, alors maintenant nous avons une trois ensemble d'éléments. Comment pouvons-nous trions la moitié gauche de cette tableau, ce qui est encore cette étape? Nous essayons de trier la gauche la moitié de la brique rouge array-- la moitié gauche de laquelle Je suis maintenant en orange. 

Eh bien, nous pourrions essayer de répéter ce processus. Donc, nous sommes encore dans le train d'essayer de trier la moitié gauche de l'éventail complet. La moitié gauche de la tableau, je vais juste de décider arbitrairement que la moitié gauche sera plus petit que la moitié droite, parce que cela se produit à composé de trois éléments. 

Et donc je vais dire que le la moitié gauche de la moitié gauche de la matrice est tout simplement l'élément cinq. Cinq, étant un seul élément tableau, nous savons comment faire le tri. Et donc cinq sont triés. Nous allons juste de déclarer que. Il est un seul ensemble d'éléments. 

Nous avons donc maintenant triée la moitié gauche de la gauche half-- ou plutôt, nous avons trié les moitié gauche de l'orange. Alors maintenant, afin de toujours complète la moitié gauche de la matrice globale, nous devons trier la moitié droite de l'orange, ou ce genre de choses. Comment fait-on cela? Eh bien, nous avons un tableau à deux éléments. Donc, nous pouvons trier la moitié gauche de la matrice, qui est de deux. Deux est un élément unique. Il est donc triée par défaut. Ensuite, nous pouvons trier la moitié droite de la partie de la matrice, l'une. Voilà en quelque sorte par défaut. 

Ceci est maintenant la première fois nous avons atteint une étape de fusion. Nous avons terminé, bien que nous sommes maintenant sorte de imbriquée down-- et que ce genre de la délicate chose avec la récursivité est, vous devez garder votre la tête sur l'endroit où nous sommes. Donc, nous avons en quelque sorte la gauche la moitié de la partie d'orange. 

Et maintenant, nous sommes dans le milieu de tri la moitié droite de la partie orange. Et dans ce processus, nous sommes maintenant sur le point d'être sur l'étape, fusionner les deux moitiés ensemble. Quand on regarde les deux moitiés du tableau, nous voyons deux et un. Quel élément est plus petit? One. 

Alors quel élément est plus petit? Eh bien, il est deux ou rien. Donc, il est deux. Alors maintenant, juste pour encadrer à nouveau où nous sommes dans le contexte, nous avons trié les la moitié gauche de l'orange et la moitié droite de l'origine. Je sais que je l'ai changé les couleurs à nouveau, mais voilà où nous en étions. Et la raison pour laquelle je fait cela est parce que ce processus est va continuer, l'itération vers le bas. Nous avons trié la gauche la moitié de l'ancien d'orange et la moitié droite de l'ex-orange. 

Maintenant, nous avons besoin de fusionner les deux moitiés ensemble aussi. Voilà l'étape que nous sommes sur. Nous considérons donc que la totalité de la éléments qui sont maintenant vert, la moitié gauche du tableau d'origine. Et nous fusionnons les selon le même procédé nous l'avons fait pour la fusion de deux et il ya un juste un moment. 

La moitié gauche, la plus petite élément sur la moitié gauche est de cinq. Le plus petit élément sur la moitié droite est un. Laquelle de ces est plus petite? One. 

Le plus petit élément sur la moitié gauche est de cinq. Le plus petit élément sur la moitié droite est de deux. Quel est le plus petit? Deux. Et puis cinq et enfin rien, on peut dire cinq. 

OK, donc grande image, nous allons prendre une pause pour un second et de comprendre où nous en sommes. Si nous avons commencé à partir de le tout début, nous ont maintenant terminé pour le tableau d'ensemble juste une étape du code pseudo ici. Nous avons trié les la moitié gauche de la matrice. 

Rappelons que l'original ordre était de cinq, deux, un. En passant par ce processus et nichent bas et en répétant, continuant à briser le problème en parties plus petites et plus petites, Nous avons maintenant terminé la première étape de la pseudo- pour l'ensemble du réseau de départ. Nous avons sélectionné sa moitié gauche. 

Alors maintenant, nous allons geler là. Et maintenant, nous allons trier le droit moitié du tableau original. Et nous allons le faire en en passant par la même itératif processus de rupture choses puis de les fusionner ensemble. 

Ainsi, la moitié gauche de la rouge, ou la moitié gauche de la moitié droite de l'original tableau, je vais dire est de trois. Encore une fois, je vais être cohérent ici. Si vous avez un nombre impair nombre d'éléments, il n'a pas vraiment d'importance si vous faites une gauche plus petite ou le droit d'un plus petit. 

Ce qui importe est que chaque fois que vous rencontrer ce problème dans la conduite une fusion, vous avez besoin d'être cohérent. Vous devez soit toujours faire une gauche plus petite ou toujours besoin de faire le côté droit inférieur. Ici, je l'ai choisi pour toujours faire de la gauche plus petite quand mon tableau, ou de mon sous-ensemble, est d'une taille étrange. 

Trois est un élément unique, et ainsi il est trié. Nous avons mis à profit cette hypothèse tout au long de notre processus jusqu'ici. Alors maintenant, nous allons trier le droit la moitié de la moitié droite, ou de la moitié droite de la rouge. 

Encore une fois, nous avons besoin de diviser cette baisse. Cela ne veut pas d'un seul ensemble d'éléments. Nous ne pouvons pas déclarer triée. Et d'abord, nous allons pour trier la moitié gauche. 

La moitié gauche est un seul élément, de sorte qu'il est en quelque sorte par défaut. Ensuite, nous allons trier le droit moitié, qui est un élément unique. Il est triée par défaut. Et maintenant, nous pouvons fusionner les deux ensemble. Quatre est plus petit, et puis six est plus petit. 

Encore une fois, qu'avons-nous fait à ce point? Nous avons trié la gauche la moitié de la moitié droite. Ou revenir à l'original des couleurs qui étaient là, nous avons trié la gauche la moitié de la plus tendre rouge. Il était à l'origine une brique sombre rouge et maintenant il est un doux rouge, ou il était d'un rouge plus doux. 

Et puis nous avons trié les la moitié droite de la rouge plus doux. Maintenant, eh bien, ils sont de nouveau en vert, juste parce que nous allons à travers un processus. Et nous avons à répéter ce à plusieurs reprises. 

Alors maintenant, nous pouvons fusionner ces deux moitiés ensemble. Et voilà ce que nous faisons ici. Donc, la ligne noire juste divisé la moitié gauche et la moitié droite de cette partie de tri. 

Nous comparons la plus petite valeur sur le côté gauche de la array-- ou excusez-moi, le plus petit La valeur de la moitié gauche à la plus petite valeur de la droite la moitié et de trouver que trois est plus petit. Et maintenant un peu d'une optimisation, à droite? Il ya en fait rien à gauche sur le côté gauche. 

Il n'y a rien restante sur le côté gauche, afin que nous puissions efficacement move-- juste nous pouvons déclarer le reste est en fait trié et juste cloue , parce que il n'y a rien d'autre à comparer. Et nous savons que le côté droit du côté droit est trié. 

OK, alors maintenant nous allons geler à nouveau et comprendre où nous en sommes dans l'histoire. Dans le tableau d'ensemble, Qu'avons-nous accompli? Nous avons effectivement accomplissons maintenant les étapes un et deux étapes. Nous avons réglé la moitié gauche, et nous avons trié la moitié droite. 

Alors maintenant, tout ce qui reste est pour nous de fusionner les deux moitiés ensemble. Donc nous comparons le plus bas valorisés chaque élément de la moitié de la matrice à son tour et continuez. On est à moins de trois, donc on va. 

Deux est inférieur à trois, de sorte que deux va. Trois est inférieur à 5, de sorte à trois va. Quatre est inférieure à 5, de sorte que quatre va. Puis cinq est inférieur à six, et six est tout ce qui reste. 

Maintenant, je sais, ce qui représente beaucoup d'étapes. Et nous avons laissé beaucoup de la mémoire dans notre sillage. Et qui est ce que ces places sont gris. Et il se sentait probablement comme ça a pris un beaucoup plus longtemps que le tri par insertion, bulle Trier, ou la sélection sorte. 

Mais en réalité, car une beaucoup de ces processus il se passe en même time-- ce qui est quelque chose que nous allons, encore une fois, parler lorsque nous parlons de récursion dans un avenir video-- Cet algorithme fait est clairement fondamentalement différent de tout nous avons vu auparavant mais est également significativement plus efficace. 

Pourquoi donc? Eh bien, dans le pire scénario, nous avons de diviser n éléments en place puis les recombiner. Mais quand on se recombinent eux, ce que nous faisons est essentiellement doubler la taille des petits tableaux. Nous avons un tas d'un élément tableaux que nous efficacement combiner en deux rangées d'éléments. Et puis nous prenons ceux deux rangées d'éléments et de les combiner ensemble dans quatre rangées d'éléments, et ainsi de suite, et ainsi de suite, et ainsi de suite, jusqu'à ce qu'on avoir un seul tableau n de l'élément. 

Mais combien doublements faut-il pour arriver à n? Pensez à l'exemple du livre de téléphone. Combien de fois avons-nous de déchirer le livre de téléphone dans la moitié, combien plus fois devrons-nous de déchirer le livre de téléphone en deux, si la taille de l'annuaire doublé? Il ya juste un, non? 

Donc, il ya une sorte de élément logarithmique ici. Mais nous avons encore au moins regarder tous les n éléments. Ainsi, dans le pire des cas, fusionner pistes Tri n log n. Nous devons regarder tous les n éléments, et nous avons de les combiner ensemble dans log n ensembles de mesures. Dans le meilleur des cas, le tableau est parfaitement réglé. C'est génial. Mais basé sur l'algorithme que nous avons ici, nous avons encore à diviser et recombiner. Bien que dans ce cas, le recombinaison est une sorte de inefficaces. Il est pas nécessaire. Mais nous allons encore à travers l'ensemble du processus de toute façon. 

Donc, dans le meilleur des cas et dans le pire des cas, cet algorithme fonctionne en n log n temps. Tri par fusion est certainement un peu plus compliqué que les autres principaux algorithmes de tri nous avons parlé CS50 mais est- sensiblement plus puissant. 

Et si jamais vous trouvez occasion de besoin ou de l'utiliser pour trier une grand ensemble de données, obtenir votre tête autour de l'idée de la récursivité va être vraiment puissant. Et ça va faire de votre programmes vraiment beaucoup plus efficace en utilisant le tri par fusion par rapport à toute autre chose. Je suis Doug Lloyd. Ceci est CS50.