1
00:00:00,000 --> 00:00:04,419
>> [Jouer de la musique]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, donc une fusion
Trier est encore un autre algorithme

4
00:00:08,460 --> 00:00:11,200
que nous pouvons utiliser pour trier
les éléments d'un tableau.

5
00:00:11,200 --> 00:00:14,480
Mais comme nous le verrons, il a un
différence très fondamentale

6
00:00:14,480 --> 00:00:17,850
de la sélection sorte, bulle
Trier, et le tri par insertion

7
00:00:17,850 --> 00:00:20,280
qui font qu'il est vraiment très intelligent.

8
00:00:20,280 --> 00:00:24,290
>> L'idée de base derrière fusion
Trier est de trier les petits tableaux

9
00:00:24,290 --> 00:00:27,430
puis combiner ces réseaux
ensemble, ou fusionner eux--

10
00:00:27,430 --> 00:00:31,440
d'où le name-- dans l'ordre.

11
00:00:31,440 --> 00:00:34,230
La façon dont fusion ne sorte
cela est en misant sur un outil

12
00:00:34,230 --> 00:00:37,290
appelé récurrence, ce qui est
nous allons parler de bientôt,

13
00:00:37,290 --> 00:00:39,720
mais nous avons pas vraiment parlé encore.

14
00:00:39,720 --> 00:00:43,010
>> Voici l'idée de base derrière le tri par fusion.

15
00:00:43,010 --> 00:00:46,320
Trier la moitié gauche du tableau,
en supposant que n est supérieur à 1.

16
00:00:46,320 --> 00:00:49,980
Et ce que je veux dire quand je dis
en supposant que n est supérieur à 1 est,

17
00:00:49,980 --> 00:00:53,970
Je pense que nous pouvons convenir que si un tableau
ne se compose que d'un seul élément,

18
00:00:53,970 --> 00:00:54,680
elle est triée.

19
00:00:54,680 --> 00:00:56,560
Nous ne devons pas réellement
pour faire quoi que ce soit.

20
00:00:56,560 --> 00:00:58,059
Nous pouvons simplement déclarer à trier.

21
00:00:58,059 --> 00:01:00,110
Il est seulement un seul élément.

22
00:01:00,110 --> 00:01:03,610
>> Donc, le pseudo, encore une fois, est
trier la moitié gauche de la matrice,

23
00:01:03,610 --> 00:01:08,590
ensuite trier la moitié droite du tableau,
puis fusionner les deux moitiés ensemble.

24
00:01:08,590 --> 00:01:11,040
Maintenant, vous pourriez être déjà
penser, il sorte de juste

25
00:01:11,040 --> 00:01:14,080
sonne comme vous mettez hors the--
vous n'êtes pas en train de faire quoi que ce soit.

26
00:01:14,080 --> 00:01:16,330
Vous dites trier la gauche
la moitié, trier la moitié droite,

27
00:01:16,330 --> 00:01:19,335
mais vous ne dites pas
moi comment vous le faites.

28
00:01:19,335 --> 00:01:22,220
>> Mais rappelez-vous que tant que
un tableau est un seul élément,

29
00:01:22,220 --> 00:01:23,705
nous pouvons déclarer triée.

30
00:01:23,705 --> 00:01:25,330
Ensuite, nous pouvons simplement les combiner.

31
00:01:25,330 --> 00:01:27,788
Et qui est en fait le
idée fondamentale derrière le tri par fusion,

32
00:01:27,788 --> 00:01:31,150
est de le décomposer afin que
vos tableaux sont de la taille d'un.

33
00:01:31,150 --> 00:01:33,430
Et puis vous reconstruisez à partir de là.

34
00:01:33,430 --> 00:01:35,910
>> Tri par fusion est définitivement
un algorithme compliqué.

35
00:01:35,910 --> 00:01:38,210
Et il est aussi un peu
compliqué à visualiser.

36
00:01:38,210 --> 00:01:41,870
Donc, je l'espère, la visualisation que je
avez ici va vous aider à suivre.

37
00:01:41,870 --> 00:01:45,640
Et je ferai de mon mieux pour raconter les choses
et de passer par cela un peu plus

38
00:01:45,640 --> 00:01:49,180
lentement que les autres
juste pour obtenir espérons votre tête

39
00:01:49,180 --> 00:01:51,800
autour des idées derrière tri par fusion.

40
00:01:51,800 --> 00:01:54,680
>> Donc, nous avons le même tableau que la
autres vidéos de algorithme de tri

41
00:01:54,680 --> 00:01:57,120
si vous avez vu eux--
un ensemble de six éléments.

42
00:01:57,120 --> 00:02:02,110
Et notre code de pseudo ici est une sorte
la moitié gauche, trier la moitié droite,

43
00:02:02,110 --> 00:02:03,890
fusionner les deux moitiés ensemble.

44
00:02:03,890 --> 00:02:09,770
Prenons donc cette brique très rouge foncé
tableau et trier la moitié gauche de celui-ci.

45
00:02:09,770 --> 00:02:13,380
>> Donc, pour le moment, nous allons
d'ignorer les trucs sur la droite.

46
00:02:13,380 --> 00:02:15,740
Il est là, mais nous sommes
pas encore cette étape.

47
00:02:15,740 --> 00:02:18,220
Nous ne sommes pas à l'espèce
moitié droite du tableau.

48
00:02:18,220 --> 00:02:21,037
Nous sommes à la gauche de tri
moitié de la matrice.

49
00:02:21,037 --> 00:02:22,870
Et juste pour le plaisir
d'être un peu plus

50
00:02:22,870 --> 00:02:26,480
clair, si je peux me référer
à quelle étape nous sommes sur,

51
00:02:26,480 --> 00:02:29,800
Je vais passer la
couleur de cet ensemble à l'orange.

52
00:02:29,800 --> 00:02:33,190
Maintenant, nous parlons toujours de la
même la moitié gauche du tableau d'origine.

53
00:02:33,190 --> 00:02:38,520
Mais je suis en espérant que, en étant en mesure de
reportez-vous aux couleurs de divers éléments,

54
00:02:38,520 --> 00:02:40,900
ça va faire un peu plus
effacer ce qui se passe ici.

55
00:02:40,900 --> 00:02:43,270
>> OK, alors maintenant nous avons une
trois ensemble d'éléments.

56
00:02:43,270 --> 00:02:46,420
Comment pouvons-nous trions la moitié gauche de cette
tableau, ce qui est encore cette étape?

57
00:02:46,420 --> 00:02:49,400
Nous essayons de trier la gauche
la moitié de la brique rouge array--

58
00:02:49,400 --> 00:02:52,410
la moitié gauche de laquelle
Je suis maintenant en orange.

59
00:02:52,410 --> 00:02:54,840
>> Eh bien, nous pourrions essayer de
répéter ce processus.

60
00:02:54,840 --> 00:02:56,756
Donc, nous sommes encore dans le
train d'essayer de trier

61
00:02:56,756 --> 00:02:58,700
la moitié gauche de l'éventail complet.

62
00:02:58,700 --> 00:03:00,450
La moitié gauche de la
tableau, je vais juste

63
00:03:00,450 --> 00:03:03,910
de décider arbitrairement que la moitié gauche
sera plus petit que la moitié droite,

64
00:03:03,910 --> 00:03:06,550
parce que cela se produit à
composé de trois éléments.

65
00:03:06,550 --> 00:03:11,260
>> Et donc je vais dire que le
la moitié gauche de la moitié gauche de la matrice

66
00:03:11,260 --> 00:03:14,050
est tout simplement l'élément cinq.

67
00:03:14,050 --> 00:03:18,360
Cinq, étant un seul élément
tableau, nous savons comment faire le tri.

68
00:03:18,360 --> 00:03:21,615
Et donc cinq sont triés.

69
00:03:21,615 --> 00:03:22,990
Nous allons juste de déclarer que.

70
00:03:22,990 --> 00:03:24,890
Il est un seul ensemble d'éléments.

71
00:03:24,890 --> 00:03:29,015
>> Nous avons donc maintenant triée la
moitié gauche de la gauche half--

72
00:03:29,015 --> 00:03:33,190
ou plutôt, nous avons trié les
moitié gauche de l'orange.

73
00:03:33,190 --> 00:03:37,970
Alors maintenant, afin de toujours complète
la moitié gauche de la matrice globale,

74
00:03:37,970 --> 00:03:43,481
nous devons trier la moitié droite
de l'orange, ou ce genre de choses.

75
00:03:43,481 --> 00:03:44,230
Comment fait-on cela?

76
00:03:44,230 --> 00:03:45,930
Eh bien, nous avons un tableau à deux éléments.

77
00:03:45,930 --> 00:03:50,470
Donc, nous pouvons trier la moitié gauche
de la matrice, qui est de deux.

78
00:03:50,470 --> 00:03:52,090
Deux est un élément unique.

79
00:03:52,090 --> 00:03:55,890
Il est donc triée par défaut.
Ensuite, nous pouvons trier la moitié droite

80
00:03:55,890 --> 00:03:58,530
de la partie de la matrice, l'une.

81
00:03:58,530 --> 00:04:00,210
Voilà en quelque sorte par défaut.

82
00:04:00,210 --> 00:04:03,610
>> Ceci est maintenant la première fois
nous avons atteint une étape de fusion.

83
00:04:03,610 --> 00:04:06,135
Nous avons terminé, bien que
nous sommes maintenant sorte de imbriquée down--

84
00:04:06,135 --> 00:04:08,420
et que ce genre de la délicate
chose avec la récursivité est,

85
00:04:08,420 --> 00:04:10,930
vous devez garder votre
la tête sur l'endroit où nous sommes.

86
00:04:10,930 --> 00:04:15,560
Donc, nous avons en quelque sorte la gauche
la moitié de la partie d'orange.

87
00:04:15,560 --> 00:04:21,280
>> Et maintenant, nous sommes dans le milieu de tri
la moitié droite de la partie orange.

88
00:04:21,280 --> 00:04:25,320
Et dans ce processus, nous sommes
maintenant sur le point d'être sur l'étape,

89
00:04:25,320 --> 00:04:27,850
fusionner les deux moitiés ensemble.

90
00:04:27,850 --> 00:04:31,700
Quand on regarde les deux moitiés
du tableau, nous voyons deux et un.

91
00:04:31,700 --> 00:04:33,880
Quel élément est plus petit?

92
00:04:33,880 --> 00:04:35,160
One.

93
00:04:35,160 --> 00:04:36,760
>> Alors quel élément est plus petit?

94
00:04:36,760 --> 00:04:38,300
Eh bien, il est deux ou rien.

95
00:04:38,300 --> 00:04:39,910
Donc, il est deux.

96
00:04:39,910 --> 00:04:43,690
Alors maintenant, juste pour encadrer à nouveau
où nous sommes dans le contexte,

97
00:04:43,690 --> 00:04:48,230
nous avons trié les
la moitié gauche de l'orange

98
00:04:48,230 --> 00:04:49,886
et la moitié droite de l'origine.

99
00:04:49,886 --> 00:04:52,510
Je sais que je l'ai changé les couleurs
à nouveau, mais voilà où nous en étions.

100
00:04:52,510 --> 00:04:54,676
Et la raison pour laquelle je fait cela
est parce que ce processus est

101
00:04:54,676 --> 00:04:57,870
va continuer, l'itération vers le bas.

102
00:04:57,870 --> 00:05:00,500
Nous avons trié la gauche
la moitié de l'ancien d'orange

103
00:05:00,500 --> 00:05:02,590
et la moitié droite de l'ex-orange.

104
00:05:02,590 --> 00:05:05,620
>> Maintenant, nous avons besoin de fusionner les
deux moitiés ensemble aussi.

105
00:05:05,620 --> 00:05:07,730
Voilà l'étape que nous sommes sur.

106
00:05:07,730 --> 00:05:11,440
Nous considérons donc que la totalité de la
éléments qui sont maintenant vert,

107
00:05:11,440 --> 00:05:12,972
la moitié gauche du tableau d'origine.

108
00:05:12,972 --> 00:05:14,680
Et nous fusionnons les
selon le même procédé

109
00:05:14,680 --> 00:05:18,660
nous l'avons fait pour la fusion de deux
et il ya un juste un moment.

110
00:05:18,660 --> 00:05:23,080
>> La moitié gauche, la plus petite
élément sur la moitié gauche est de cinq.

111
00:05:23,080 --> 00:05:25,620
Le plus petit élément sur
la moitié droite est un.

112
00:05:25,620 --> 00:05:27,370
Laquelle de ces est plus petite?

113
00:05:27,370 --> 00:05:29,260
One.

114
00:05:29,260 --> 00:05:32,250
>> Le plus petit élément sur
la moitié gauche est de cinq.

115
00:05:32,250 --> 00:05:35,540
Le plus petit élément sur
la moitié droite est de deux.

116
00:05:35,540 --> 00:05:36,970
Quel est le plus petit?

117
00:05:36,970 --> 00:05:38,160
Deux.

118
00:05:38,160 --> 00:05:41,540
Et puis cinq et enfin
rien, on peut dire cinq.

119
00:05:41,540 --> 00:05:43,935
>> OK, donc grande image, nous allons
prendre une pause pour un second

120
00:05:43,935 --> 00:05:46,080
et de comprendre où nous en sommes.

121
00:05:46,080 --> 00:05:48,580
Si nous avons commencé à partir de
le tout début, nous

122
00:05:48,580 --> 00:05:51,640
ont maintenant terminé pour
le tableau d'ensemble juste

123
00:05:51,640 --> 00:05:53,810
une étape du code pseudo ici.

124
00:05:53,810 --> 00:05:56,645
Nous avons trié les
la moitié gauche de la matrice.

125
00:05:56,645 --> 00:05:59,490
>> Rappelons que l'original
ordre était de cinq, deux, un.

126
00:05:59,490 --> 00:06:02,570
En passant par ce processus
et nichent bas et en répétant,

127
00:06:02,570 --> 00:06:05,990
continuant à briser le problème
en parties plus petites et plus petites,

128
00:06:05,990 --> 00:06:09,670
Nous avons maintenant terminé
la première étape de la pseudo-

129
00:06:09,670 --> 00:06:13,940
pour l'ensemble du réseau de départ.

130
00:06:13,940 --> 00:06:16,670
Nous avons sélectionné sa moitié gauche.

131
00:06:16,670 --> 00:06:18,670
>> Alors maintenant, nous allons geler là.

132
00:06:18,670 --> 00:06:23,087
Et maintenant, nous allons trier le droit
moitié du tableau original.

133
00:06:23,087 --> 00:06:25,670
Et nous allons le faire en
en passant par la même itératif

134
00:06:25,670 --> 00:06:30,630
processus de rupture choses
puis de les fusionner ensemble.

135
00:06:30,630 --> 00:06:34,290
>> Ainsi, la moitié gauche de la
rouge, ou la moitié gauche

136
00:06:34,290 --> 00:06:38,830
de la moitié droite de l'original
tableau, je vais dire est de trois.

137
00:06:38,830 --> 00:06:40,312
Encore une fois, je vais être cohérent ici.

138
00:06:40,312 --> 00:06:42,020
Si vous avez un nombre impair
nombre d'éléments, il

139
00:06:42,020 --> 00:06:44,478
n'a pas vraiment d'importance si
vous faites une gauche plus petite

140
00:06:44,478 --> 00:06:45,620
ou le droit d'un plus petit.

141
00:06:45,620 --> 00:06:49,230
>> Ce qui importe est que chaque fois que vous
rencontrer ce problème dans la conduite

142
00:06:49,230 --> 00:06:51,422
une fusion, vous avez besoin d'être cohérent.

143
00:06:51,422 --> 00:06:53,505
Vous devez soit toujours
faire une gauche plus petite

144
00:06:53,505 --> 00:06:55,421
ou toujours besoin de faire
le côté droit inférieur.

145
00:06:55,421 --> 00:06:57,720
Ici, je l'ai choisi pour toujours
faire de la gauche plus petite

146
00:06:57,720 --> 00:07:04,380
quand mon tableau, ou de mon
sous-ensemble, est d'une taille étrange.

147
00:07:04,380 --> 00:07:07,420
>> Trois est un élément unique,
et ainsi il est trié.

148
00:07:07,420 --> 00:07:10,860
Nous avons mis à profit cette hypothèse
tout au long de notre processus jusqu'ici.

149
00:07:10,860 --> 00:07:15,020
Alors maintenant, nous allons trier le droit
la moitié de la moitié droite,

150
00:07:15,020 --> 00:07:18,210
ou de la moitié droite de la rouge.

151
00:07:18,210 --> 00:07:20,390
>> Encore une fois, nous avons besoin de diviser cette baisse.

152
00:07:20,390 --> 00:07:21,910
Cela ne veut pas d'un seul ensemble d'éléments.

153
00:07:21,910 --> 00:07:23,970
Nous ne pouvons pas déclarer triée.

154
00:07:23,970 --> 00:07:27,060
Et d'abord, nous allons
pour trier la moitié gauche.

155
00:07:27,060 --> 00:07:31,620
>> La moitié gauche est un seul élément,
de sorte qu'il est en quelque sorte par défaut.

156
00:07:31,620 --> 00:07:34,840
Ensuite, nous allons trier le droit
moitié, qui est un élément unique.

157
00:07:34,840 --> 00:07:41,250
Il est triée par défaut. Et maintenant,
nous pouvons fusionner les deux ensemble.

158
00:07:41,250 --> 00:07:45,820
Quatre est plus petit, et
puis six est plus petit.

159
00:07:45,820 --> 00:07:48,870
>> Encore une fois, qu'avons-nous fait à ce point?

160
00:07:48,870 --> 00:07:52,512
Nous avons trié la gauche
la moitié de la moitié droite.

161
00:07:52,512 --> 00:07:54,720
Ou revenir à l'original
des couleurs qui étaient là,

162
00:07:54,720 --> 00:07:57,875
nous avons trié la gauche
la moitié de la plus tendre rouge.

163
00:07:57,875 --> 00:08:00,416
Il était à l'origine une brique sombre
rouge et maintenant il est un doux rouge,

164
00:08:00,416 --> 00:08:02,350
ou il était d'un rouge plus doux.

165
00:08:02,350 --> 00:08:05,145
>> Et puis nous avons trié les
la moitié droite de la rouge plus doux.

166
00:08:05,145 --> 00:08:08,270
Maintenant, eh bien, ils sont de nouveau en vert, juste
parce que nous allons à travers un processus.

167
00:08:08,270 --> 00:08:10,720
Et nous avons à répéter
ce à plusieurs reprises.

168
00:08:10,720 --> 00:08:14,695
>> Alors maintenant, nous pouvons fusionner ces
deux moitiés ensemble.

169
00:08:14,695 --> 00:08:15,820
Et voilà ce que nous faisons ici.

170
00:08:15,820 --> 00:08:17,653
Donc, la ligne noire juste
divisé la moitié gauche

171
00:08:17,653 --> 00:08:19,690
et la moitié droite de cette partie de tri.

172
00:08:19,690 --> 00:08:24,310
>> Nous comparons la plus petite valeur
sur le côté gauche de la array--

173
00:08:24,310 --> 00:08:26,710
ou excusez-moi, le plus petit
La valeur de la moitié gauche

174
00:08:26,710 --> 00:08:30,790
à la plus petite valeur de la droite
la moitié et de trouver que trois est plus petit.

175
00:08:30,790 --> 00:08:32,530
Et maintenant un peu d'une optimisation, à droite?

176
00:08:32,530 --> 00:08:35,175
Il ya en fait rien
à gauche sur le côté gauche.

177
00:08:35,175 --> 00:08:37,440
>> Il n'y a rien restante
sur le côté gauche,

178
00:08:37,440 --> 00:08:40,877
afin que nous puissions efficacement
move-- juste nous pouvons déclarer

179
00:08:40,877 --> 00:08:42,960
le reste est en fait
trié et juste cloue

180
00:08:42,960 --> 00:08:45,126
, parce que il n'y a rien
d'autre à comparer.

181
00:08:45,126 --> 00:08:49,140
Et nous savons que le côté droit
du côté droit est trié.

182
00:08:49,140 --> 00:08:52,770
>> OK, alors maintenant nous allons geler à nouveau et
comprendre où nous en sommes dans l'histoire.

183
00:08:52,770 --> 00:08:56,120
Dans le tableau d'ensemble,
Qu'avons-nous accompli?

184
00:08:56,120 --> 00:08:58,790
Nous avons effectivement accomplissons
maintenant les étapes un et deux étapes.

185
00:08:58,790 --> 00:09:03,300
Nous avons réglé la moitié gauche, et
nous avons trié la moitié droite.

186
00:09:03,300 --> 00:09:08,210
>> Alors maintenant, tout ce qui reste est pour nous
de fusionner les deux moitiés ensemble.

187
00:09:08,210 --> 00:09:11,670
Donc nous comparons le plus bas valorisés
chaque élément de la moitié de la matrice

188
00:09:11,670 --> 00:09:13,510
à son tour et continuez.

189
00:09:13,510 --> 00:09:16,535
On est à moins de trois, donc on va.

190
00:09:16,535 --> 00:09:19,770
>> Deux est inférieur à trois, de sorte que deux va.

191
00:09:19,770 --> 00:09:22,740
Trois est inférieur à 5, de sorte à trois va.

192
00:09:22,740 --> 00:09:25,820
Quatre est inférieure à 5, de sorte que quatre va.

193
00:09:25,820 --> 00:09:30,210
Puis cinq est inférieur à six,
et six est tout ce qui reste.

194
00:09:30,210 --> 00:09:31,820
>> Maintenant, je sais, ce qui représente beaucoup d'étapes.

195
00:09:31,820 --> 00:09:33,636
Et nous avons laissé beaucoup
de la mémoire dans notre sillage.

196
00:09:33,636 --> 00:09:35,260
Et qui est ce que ces places sont gris.

197
00:09:35,260 --> 00:09:40,540
Et il se sentait probablement comme ça a pris un
beaucoup plus longtemps que le tri par insertion, bulle

198
00:09:40,540 --> 00:09:42,660
Trier, ou la sélection sorte.

199
00:09:42,660 --> 00:09:45,330
>> Mais en réalité, car une
beaucoup de ces processus

200
00:09:45,330 --> 00:09:48,260
il se passe en même time--
ce qui est quelque chose que nous allons, encore une fois,

201
00:09:48,260 --> 00:09:51,100
parler lorsque nous parlons de
récursion dans un avenir video--

202
00:09:51,100 --> 00:09:53,799
Cet algorithme fait
est clairement fondamentalement

203
00:09:53,799 --> 00:09:55,590
différent de tout
nous avons vu auparavant

204
00:09:55,590 --> 00:09:58,820
mais est également significativement
plus efficace.

205
00:09:58,820 --> 00:09:59,532
>> Pourquoi donc?

206
00:09:59,532 --> 00:10:01,240
Eh bien, dans le pire
scénario, nous avons

207
00:10:01,240 --> 00:10:04,830
de diviser n éléments en place
puis les recombiner.

208
00:10:04,830 --> 00:10:06,680
Mais quand on se recombinent
eux, ce que nous faisons

209
00:10:06,680 --> 00:10:11,110
est essentiellement doubler la
taille des petits tableaux.

210
00:10:11,110 --> 00:10:14,260
Nous avons un tas d'un élément
tableaux que nous efficacement

211
00:10:14,260 --> 00:10:16,290
combiner en deux rangées d'éléments.

212
00:10:16,290 --> 00:10:18,590
Et puis nous prenons ceux
deux rangées d'éléments

213
00:10:18,590 --> 00:10:21,890
et de les combiner ensemble dans
quatre rangées d'éléments, et ainsi de suite,

214
00:10:21,890 --> 00:10:26,130
et ainsi de suite, et ainsi de suite, jusqu'à ce qu'on
avoir un seul tableau n de l'élément.

215
00:10:26,130 --> 00:10:29,910
>> Mais combien doublements
faut-il pour arriver à n?

216
00:10:29,910 --> 00:10:31,460
Pensez à l'exemple du livre de téléphone.

217
00:10:31,460 --> 00:10:34,490
Combien de fois avons-nous de déchirer
le livre de téléphone dans la moitié, combien plus

218
00:10:34,490 --> 00:10:38,370
fois devrons-nous de déchirer le livre de téléphone
en deux, si la taille de l'annuaire

219
00:10:38,370 --> 00:10:39,680
doublé?

220
00:10:39,680 --> 00:10:41,960
Il ya juste un, non?

221
00:10:41,960 --> 00:10:45,360
>> Donc, il ya une sorte de
élément logarithmique ici.

222
00:10:45,360 --> 00:10:48,590
Mais nous avons encore au moins
regarder tous les n éléments.

223
00:10:48,590 --> 00:10:53,860
Ainsi, dans le pire des cas,
fusionner pistes Tri n log n.

224
00:10:53,860 --> 00:10:56,160
Nous devons regarder
tous les n éléments,

225
00:10:56,160 --> 00:11:02,915
et nous avons de les combiner
ensemble dans log n ensembles de mesures.

226
00:11:02,915 --> 00:11:05,290
Dans le meilleur des cas,
le tableau est parfaitement réglé.

227
00:11:05,290 --> 00:11:06,300
C'est génial.

228
00:11:06,300 --> 00:11:09,980
Mais basé sur l'algorithme que nous avons ici,
nous avons encore à diviser et recombiner.

229
00:11:09,980 --> 00:11:13,290
Bien que dans ce cas, le
recombinaison est une sorte de inefficaces.

230
00:11:13,290 --> 00:11:14,720
Il est pas nécessaire.

231
00:11:14,720 --> 00:11:17,580
Mais nous allons encore à travers
l'ensemble du processus de toute façon.

232
00:11:17,580 --> 00:11:21,290
>> Donc, dans le meilleur des cas
et dans le pire des cas,

233
00:11:21,290 --> 00:11:24,970
cet algorithme fonctionne en n log n temps.

234
00:11:24,970 --> 00:11:29,130
Tri par fusion est certainement un peu plus compliqué
que les autres principaux algorithmes de tri

235
00:11:29,130 --> 00:11:33,470
nous avons parlé CS50 mais est-
sensiblement plus puissant.

236
00:11:33,470 --> 00:11:35,400
>> Et si jamais vous trouvez
occasion de besoin

237
00:11:35,400 --> 00:11:38,480
ou de l'utiliser pour trier une
grand ensemble de données, obtenir

238
00:11:38,480 --> 00:11:41,940
votre tête autour de l'idée de la récursivité
va être vraiment puissant.

239
00:11:41,940 --> 00:11:45,270
Et ça va faire de votre
programmes vraiment beaucoup plus efficace

240
00:11:45,270 --> 00:11:48,700
en utilisant le tri par fusion par rapport à toute autre chose.

241
00:11:48,700 --> 00:11:49,640
Je suis Doug Lloyd.

242
00:11:49,640 --> 00:11:51,970
Ceci est CS50.

243
00:11:51,970 --> 00:11:53,826