1
00:00:00,000 --> 00:00:04,419
>> [RIPRODUZIONE DI BRANI MUSICALI]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, così un'unione
tipo è un altro algoritmo

4
00:00:08,460 --> 00:00:11,200
che possiamo usare per risolvere
gli elementi di un array.

5
00:00:11,200 --> 00:00:14,480
Ma, come vedremo, che ha un
differenza molto fondamentale

6
00:00:14,480 --> 00:00:17,850
dalla selezione tipo, bolla
ordinamento e insertion sort

7
00:00:17,850 --> 00:00:20,280
che lo rendono davvero molto intelligente.

8
00:00:20,280 --> 00:00:24,290
>> L'idea di base dietro merge
tipo è quello di ordinare le matrici più piccoli

9
00:00:24,290 --> 00:00:27,430
e poi combinare questi array
insieme, o unire them--

10
00:00:27,430 --> 00:00:31,440
da qui il nome-- in modo ordinato.

11
00:00:31,440 --> 00:00:34,230
Il modo in cui si fondono fa specie
questo è sfruttando uno strumento

12
00:00:34,230 --> 00:00:37,290
chiamato ricorsione, che è ciò che
stiamo andando a parlare di presto,

13
00:00:37,290 --> 00:00:39,720
ma non abbiamo ancora parlato ancora.

14
00:00:39,720 --> 00:00:43,010
>> Ecco l'idea di base dietro merge sort.

15
00:00:43,010 --> 00:00:46,320
Ordina la metà sinistra della matrice,
supponendo n è maggiore di 1.

16
00:00:46,320 --> 00:00:49,980
E quello che intendo quando dico
supponendo n è maggiore di 1 è,

17
00:00:49,980 --> 00:00:53,970
Penso che possiamo essere d'accordo che se una matrice
soltanto costituito da un unico elemento,

18
00:00:53,970 --> 00:00:54,680
è ordinato.

19
00:00:54,680 --> 00:00:56,560
Noi in realtà non serve
a tutto pur di esso.

20
00:00:56,560 --> 00:00:58,059
Possiamo solo dichiarare da ordinare.

21
00:00:58,059 --> 00:01:00,110
E 'solo un singolo elemento.

22
00:01:00,110 --> 00:01:03,610
>> Così pseudocodice, di nuovo, è
ordinare la metà di sinistra della matrice,

23
00:01:03,610 --> 00:01:08,590
poi ordinare la metà destra della matrice,
quindi unire le due metà insieme.

24
00:01:08,590 --> 00:01:11,040
Ora, già si potrebbe essere
pensando, che tipo di solo

25
00:01:11,040 --> 00:01:14,080
suona come si sta mettendo fuori the--
non stai realmente facendo nulla.

26
00:01:14,080 --> 00:01:16,330
Stai dicendo che ordinare la sinistra
la metà, ordinare la metà destra,

27
00:01:16,330 --> 00:01:19,335
ma tu non stai dicendo
me come si sta facendo.

28
00:01:19,335 --> 00:01:22,220
>> Ma ricordate che finché
un array è un singolo elemento,

29
00:01:22,220 --> 00:01:23,705
possiamo dichiarare che risolto.

30
00:01:23,705 --> 00:01:25,330
Allora possiamo solo combinarli insieme.

31
00:01:25,330 --> 00:01:27,788
E questo è in realtà il
idea fondamentale dietro merge sort,

32
00:01:27,788 --> 00:01:31,150
è una scomposizione in modo che
gli array sono di dimensioni uno.

33
00:01:31,150 --> 00:01:33,430
E poi si ricostruisce da lì.

34
00:01:33,430 --> 00:01:35,910
>> Merge sort è sicuramente
un algoritmo complicato.

35
00:01:35,910 --> 00:01:38,210
Ed è anche un po '
complicato da visualizzare.

36
00:01:38,210 --> 00:01:41,870
Così si spera, la visualizzazione che io
avete qui vi aiuterà a seguire insieme.

37
00:01:41,870 --> 00:01:45,640
E farò del mio meglio per raccontare le cose
e procedere attraverso questo un po 'più

38
00:01:45,640 --> 00:01:49,180
lentamente rispetto gli altri
solo per ottenere la vostra testa si spera

39
00:01:49,180 --> 00:01:51,800
intorno alle idee che stanno dietro merge sort.

40
00:01:51,800 --> 00:01:54,680
>> Così abbiamo la stessa matrice come il
altri video algoritmo di ordinamento

41
00:01:54,680 --> 00:01:57,120
se avete visto them--
un array di sei elementi.

42
00:01:57,120 --> 00:02:02,110
E il nostro codice pseudocodice qui è sorta
la metà di sinistra, ordinare la metà destra,

43
00:02:02,110 --> 00:02:03,890
unire le due metà insieme.

44
00:02:03,890 --> 00:02:09,770
Quindi cerchiamo di prendere questo rosso mattone molto scuro
array e ordinare la metà di sinistra di esso.

45
00:02:09,770 --> 00:02:13,380
>> Così, per il momento, stiamo andando
di ignorare le cose di destra.

46
00:02:13,380 --> 00:02:15,740
E 'lì, ma siamo
non a ma questo passo.

47
00:02:15,740 --> 00:02:18,220
Non siamo in genere il
metà destra della matrice.

48
00:02:18,220 --> 00:02:21,037
Siamo al sorta sinistra
metà dell'array.

49
00:02:21,037 --> 00:02:22,870
E solo per il gusto
di essere un po 'più

50
00:02:22,870 --> 00:02:26,480
chiaro, così posso fare riferimento
a quale punto siamo su,

51
00:02:26,480 --> 00:02:29,800
Ho intenzione di cambiare la
colore di questo insieme di arancio.

52
00:02:29,800 --> 00:02:33,190
Ora, stiamo ancora parlando della
stessa metà sinistra della matrice originale.

53
00:02:33,190 --> 00:02:38,520
Ma spero che, essendo in grado di
fare riferimento ai colori dei vari elementi,

54
00:02:38,520 --> 00:02:40,900
che ti farà un po 'più
chiaro quello che sta succedendo qui.

55
00:02:40,900 --> 00:02:43,270
>> OK, ora abbiamo un
tre schiera di elementi.

56
00:02:43,270 --> 00:02:46,420
Come si fa a ordinare la metà di sinistra di questo
array, che è ancora questo passo?

57
00:02:46,420 --> 00:02:49,400
Stiamo cercando di risolvere la sinistra
metà del array-- rosso mattone

58
00:02:49,400 --> 00:02:52,410
la metà sinistra di cui
Ora ho di colore arancione.

59
00:02:52,410 --> 00:02:54,840
>> Beh, potremmo cercare di
ripetere questo processo.

60
00:02:54,840 --> 00:02:56,756
Quindi siamo ancora in
mezzo di cercare di ordinare

61
00:02:56,756 --> 00:02:58,700
la metà sinistra della matrice completa.

62
00:02:58,700 --> 00:03:00,450
La metà sinistra del
array, sto solo andando

63
00:03:00,450 --> 00:03:03,910
decidere arbitrariamente che la metà sinistra
sarà inferiore alla metà di destra,

64
00:03:03,910 --> 00:03:06,550
perché questo accade a
costituita da tre elementi.

65
00:03:06,550 --> 00:03:11,260
>> E così ho intenzione di dire che la
metà sinistra della metà sinistra della matrice

66
00:03:11,260 --> 00:03:14,050
è solo l'elemento cinque.

67
00:03:14,050 --> 00:03:18,360
Cinque, essendo un unico elemento
array, sappiamo come risolverlo.

68
00:03:18,360 --> 00:03:21,615
E così cinque è ordinato.

69
00:03:21,615 --> 00:03:22,990
Stiamo solo andando a dichiarare che.

70
00:03:22,990 --> 00:03:24,890
Si tratta di un unico array elemento.

71
00:03:24,890 --> 00:03:29,015
>> Così ora abbiamo risolto il
la metà sinistra del half-- sinistra

72
00:03:29,015 --> 00:03:33,190
o meglio, abbiamo risolto il
metà sinistra arancione.

73
00:03:33,190 --> 00:03:37,970
Così ora, in modo da ancora completo
metà sinistra della matrice globale,

74
00:03:37,970 --> 00:03:43,481
abbiamo bisogno di ordinare la metà destra
del arancio, o questa roba.

75
00:03:43,481 --> 00:03:44,230
Come lo facciamo?

76
00:03:44,230 --> 00:03:45,930
Beh, abbiamo un array di due elementi.

77
00:03:45,930 --> 00:03:50,470
Così possiamo ordinare la metà di sinistra
della matrice, che è due.

78
00:03:50,470 --> 00:03:52,090
Due è un singolo elemento.

79
00:03:52,090 --> 00:03:55,890
Quindi è ordinato per impostazione predefinita.
Poi possiamo ordinare la metà destra

80
00:03:55,890 --> 00:03:58,530
di quella parte della matrice, quella.

81
00:03:58,530 --> 00:04:00,210
Questo è una sorta di default.

82
00:04:00,210 --> 00:04:03,610
>> Questo è ora la prima volta
abbiamo raggiunto un passo di unione.

83
00:04:03,610 --> 00:04:06,135
Abbiamo completato, anche se
ora stiamo tipo di annidati down--

84
00:04:06,135 --> 00:04:08,420
e questo è una specie di difficile
cosa con la ricorsione è,

85
00:04:08,420 --> 00:04:10,930
è necessario mantenere la vostra
testa su dove ci troviamo.

86
00:04:10,930 --> 00:04:15,560
Così abbiamo sorta di sinistra
la metà della porzione arancione.

87
00:04:15,560 --> 00:04:21,280
>> E ora, siamo nel bel mezzo di di smistamento
la metà destra della porzione arancione.

88
00:04:21,280 --> 00:04:25,320
E in questo processo, siamo
ora sta per essere sul gradino,

89
00:04:25,320 --> 00:04:27,850
unire le due metà insieme.

90
00:04:27,850 --> 00:04:31,700
Quando guardiamo le due metà
dell'array, vediamo due e uno.

91
00:04:31,700 --> 00:04:33,880
Quale elemento è più piccolo?

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

93
00:04:35,160 --> 00:04:36,760
>> Allora quale elemento è più piccolo?

94
00:04:36,760 --> 00:04:38,300
Beh, è ​​due o nulla.

95
00:04:38,300 --> 00:04:39,910
Quindi è due.

96
00:04:39,910 --> 00:04:43,690
Così ora, solo per inquadrare di nuovo
dove siamo nel contesto,

97
00:04:43,690 --> 00:04:48,230
abbiamo ordinato il
metà sinistra del arancio

98
00:04:48,230 --> 00:04:49,886
e la metà destra dell'origine.

99
00:04:49,886 --> 00:04:52,510
So che ho cambiato i colori
ancora una volta, ma che è dove siamo stati.

100
00:04:52,510 --> 00:04:54,676
E la ragione per cui ho fatto questo
è perché questo processo è

101
00:04:54,676 --> 00:04:57,870
intenzione di andare avanti, l'iterazione giù.

102
00:04:57,870 --> 00:05:00,500
Abbiamo risolto il sinistro
la metà del primo arancione

103
00:05:00,500 --> 00:05:02,590
e la metà destra del primo arancione.

104
00:05:02,590 --> 00:05:05,620
>> Ora, abbiamo bisogno di unire quelli
due metà insieme troppo.

105
00:05:05,620 --> 00:05:07,730
Questo è il passo che siamo su.

106
00:05:07,730 --> 00:05:11,440
Così noi consideriamo tutto il
elementi che sono ora verde,

107
00:05:11,440 --> 00:05:12,972
la metà sinistra della matrice originale.

108
00:05:12,972 --> 00:05:14,680
E ci fondiamo quelli
utilizzando lo stesso processo

109
00:05:14,680 --> 00:05:18,660
abbiamo fatto per la fusione di due
e uno appena un attimo fa.

110
00:05:18,660 --> 00:05:23,080
>> La metà sinistra, il più piccolo
elemento sulla metà sinistra è cinque.

111
00:05:23,080 --> 00:05:25,620
Il più piccolo elemento
la metà destra è uno.

112
00:05:25,620 --> 00:05:27,370
Quale di questi è più piccolo?

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

114
00:05:29,260 --> 00:05:32,250
>> Il più piccolo elemento
la metà sinistra è cinque.

115
00:05:32,250 --> 00:05:35,540
Il più piccolo elemento
la metà destra è due.

116
00:05:35,540 --> 00:05:36,970
Qual è il più piccolo?

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

118
00:05:38,160 --> 00:05:41,540
E poi, infine, cinque e
nulla, possiamo dire cinque.

119
00:05:41,540 --> 00:05:43,935
>> OK, così grande immagine, diamo
prendersi una pausa per un secondo

120
00:05:43,935 --> 00:05:46,080
e capire dove siamo.

121
00:05:46,080 --> 00:05:48,580
Se siamo partiti
Fin dall'inizio, abbiamo

122
00:05:48,580 --> 00:05:51,640
hanno ormai completato per
la matrice complessiva appena

123
00:05:51,640 --> 00:05:53,810
un passo del codice pseudocodice qui.

124
00:05:53,810 --> 00:05:56,645
Abbiamo ordinato la
metà sinistra della matrice.

125
00:05:56,645 --> 00:05:59,490
>> Ricordiamo che l'originale
ordine era cinque, due, uno.

126
00:05:59,490 --> 00:06:02,570
Passando attraverso questo processo
e nidificazione giù e ripetendo,

127
00:06:02,570 --> 00:06:05,990
continuando a rompere il problema
in parti più piccole,

128
00:06:05,990 --> 00:06:09,670
abbiamo completato
passo uno dei pseudocodice

129
00:06:09,670 --> 00:06:13,940
per l'intero array di partenza.

130
00:06:13,940 --> 00:06:16,670
Abbiamo ordinato la sua metà sinistra.

131
00:06:16,670 --> 00:06:18,670
>> Così ora cerchiamo di congelare lì.

132
00:06:18,670 --> 00:06:23,087
E ora diamo ordinare il giusto
metà dell'array originale.

133
00:06:23,087 --> 00:06:25,670
E abbiamo intenzione di farlo da
passando attraverso lo stesso iterativo

134
00:06:25,670 --> 00:06:30,630
processo di rompere le cose
e quindi unendo insieme.

135
00:06:30,630 --> 00:06:34,290
>> Quindi la metà sinistra del
rosso, o la metà sinistra

136
00:06:34,290 --> 00:06:38,830
della metà destra dell'originale
array, ho intenzione di dire è di tre.

137
00:06:38,830 --> 00:06:40,312
Ancora una volta, devo essere coerente qui.

138
00:06:40,312 --> 00:06:42,020
Se si dispone di una strana
numero di elementi,

139
00:06:42,020 --> 00:06:44,478
in realtà non importa se
a fare la sinistra più piccolo

140
00:06:44,478 --> 00:06:45,620
o destra più piccola.

141
00:06:45,620 --> 00:06:49,230
>> Ciò che conta è che ogni volta che
verificare questo problema nella conduzione

142
00:06:49,230 --> 00:06:51,422
una fusione, è necessario essere coerenti.

143
00:06:51,422 --> 00:06:53,505
Si sia sempre necessario
fare una lato sinistro più piccolo

144
00:06:53,505 --> 00:06:55,421
o sempre bisogno di fare
destra più piccola.

145
00:06:55,421 --> 00:06:57,720
Qui, ho scelto di sempre
rendere il lato sinistro più piccolo

146
00:06:57,720 --> 00:07:04,380
quando la mia matrice, o il mio
sub-array, è di una dimensione dispari.

147
00:07:04,380 --> 00:07:07,420
>> Tre è un singolo elemento,
e così è ordinato.

148
00:07:07,420 --> 00:07:10,860
Abbiamo sfruttato questa ipotesi
durante tutto il nostro processo finora.

149
00:07:10,860 --> 00:07:15,020
Così ora cerchiamo di ordinare il giusto
metà della metà destra,

150
00:07:15,020 --> 00:07:18,210
o la metà destra del rosso.

151
00:07:18,210 --> 00:07:20,390
>> Ancora una volta, abbiamo bisogno di dividere questo in giù.

152
00:07:20,390 --> 00:07:21,910
Questo non è un singolo elemento dell'array.

153
00:07:21,910 --> 00:07:23,970
Non possiamo dichiarare risolto.

154
00:07:23,970 --> 00:07:27,060
E così prima, stiamo andando
per ordinare la metà sinistra.

155
00:07:27,060 --> 00:07:31,620
>> La metà sinistra è un singolo elemento,
quindi è una sorta di default.

156
00:07:31,620 --> 00:07:34,840
Poi andremo a ordinare la destra
mezzo, che è un singolo elemento.

157
00:07:34,840 --> 00:07:41,250
E 'ordinato per impostazione predefinita. E adesso,
possiamo unire quei due insieme.

158
00:07:41,250 --> 00:07:45,820
Four è più piccolo, e
allora sei è più piccolo.

159
00:07:45,820 --> 00:07:48,870
>> Anche in questo caso, quello che abbiamo fatto a questo punto?

160
00:07:48,870 --> 00:07:52,512
Abbiamo risolto il sinistro
metà della metà destra.

161
00:07:52,512 --> 00:07:54,720
O tornare a quella originale
colori che erano lì,

162
00:07:54,720 --> 00:07:57,875
abbiamo risolto sinistra
metà rosso morbido.

163
00:07:57,875 --> 00:08:00,416
In origine era un mattone scuro
rosso e ora è un più morbido rosso,

164
00:08:00,416 --> 00:08:02,350
o che fosse un rosso morbido.

165
00:08:02,350 --> 00:08:05,145
>> E allora abbiamo risolto il
metà destra rosso morbido.

166
00:08:05,145 --> 00:08:08,270
Ora, bene, sono di nuovo verde, appena
perché noi stiamo attraversando un processo.

167
00:08:08,270 --> 00:08:10,720
E dobbiamo ripetere
più e più.

168
00:08:10,720 --> 00:08:14,695
>> Così ora siamo in grado di unire quelli
due metà insieme.

169
00:08:14,695 --> 00:08:15,820
E questo è quello che facciamo qui.

170
00:08:15,820 --> 00:08:17,653
Così la linea nera appena
diviso la metà sinistra

171
00:08:17,653 --> 00:08:19,690
e la metà destra di questa parte tipo.

172
00:08:19,690 --> 00:08:24,310
>> Confrontiamo il valore più piccolo
sul lato sinistro della array--

173
00:08:24,310 --> 00:08:26,710
o mi scusi, la più piccola
valore della metà sinistra

174
00:08:26,710 --> 00:08:30,790
al valore minimo del diritto
mezzo e scoprire che tre è più piccolo.

175
00:08:30,790 --> 00:08:32,530
Ed ora un po 'di ottimizzazione, giusto?

176
00:08:32,530 --> 00:08:35,175
In realtà c'è niente
sinistra sul lato sinistro.

177
00:08:35,175 --> 00:08:37,440
>> Non c'è niente rimanente
sul lato sinistro,

178
00:08:37,440 --> 00:08:40,877
in modo che possiamo in modo efficiente
solo move-- possiamo dichiarare

179
00:08:40,877 --> 00:08:42,960
il resto è effettivamente
ordinati e appena virare essa

180
00:08:42,960 --> 00:08:45,126
su, perché non c'è niente
altro da confrontare.

181
00:08:45,126 --> 00:08:49,140
E sappiamo che il lato destro
del lato destro è ordinato.

182
00:08:49,140 --> 00:08:52,770
>> OK, ora cerchiamo di congelare di nuovo e
capire dove siamo nella storia.

183
00:08:52,770 --> 00:08:56,120
Nella matrice complessiva,
cosa abbiamo realizzato?

184
00:08:56,120 --> 00:08:58,790
Abbiamo effettivamente realizzare
Ora passi uno e fase due.

185
00:08:58,790 --> 00:09:03,300
Abbiamo risolto la metà sinistra, e
abbiamo risolto la metà destra.

186
00:09:03,300 --> 00:09:08,210
>> Così ora, tutto ciò che rimane è per noi
di fondere queste due metà insieme.

187
00:09:08,210 --> 00:09:11,670
Quindi mettiamo a confronto il più basso valorizzati
elemento di ciascuna metà della matrice

188
00:09:11,670 --> 00:09:13,510
a sua volta, e procedere.

189
00:09:13,510 --> 00:09:16,535
Uno è inferiore a tre, così si va.

190
00:09:16,535 --> 00:09:19,770
>> Due è inferiore a tre, così due va.

191
00:09:19,770 --> 00:09:22,740
Tre è inferiore a 5, quindi tre tentativi.

192
00:09:22,740 --> 00:09:25,820
Quattro è meno di 5, quindi quattro va.

193
00:09:25,820 --> 00:09:30,210
Poi cinque è inferiore a sei,
e sei è tutto ciò che rimane.

194
00:09:30,210 --> 00:09:31,820
>> Ora, lo so, che era un sacco di passi.

195
00:09:31,820 --> 00:09:33,636
E abbiamo lasciato un sacco
della memoria nella nostra scia.

196
00:09:33,636 --> 00:09:35,260
Ed è quello che i quadrati grigi sono.

197
00:09:35,260 --> 00:09:40,540
E probabilmente sembrava che ha preso un
molto più lungo di insertion sort, bolla

198
00:09:40,540 --> 00:09:42,660
sorta, o la selezione sorta.

199
00:09:42,660 --> 00:09:45,330
>> Ma in realtà, perché un
Molti di questi processi

200
00:09:45,330 --> 00:09:48,260
stanno accadendo allo stesso tempo--
che è qualcosa faremo, ancora una volta,

201
00:09:48,260 --> 00:09:51,100
parlare quando si parla di
ricorsione in un futuro video--

202
00:09:51,100 --> 00:09:53,799
questo algoritmo in realtà
chiaramente è fondamentalmente

203
00:09:53,799 --> 00:09:55,590
diverso da qualsiasi cosa
abbiamo visto prima

204
00:09:55,590 --> 00:09:58,820
ma è anche significativamente
più efficiente.

205
00:09:58,820 --> 00:09:59,532
>> Come mai?

206
00:09:59,532 --> 00:10:01,240
Ebbene, nel peggiore
ipotesi, abbiamo

207
00:10:01,240 --> 00:10:04,830
dividere n elementi su
e poi ricombinare.

208
00:10:04,830 --> 00:10:06,680
Ma quando abbiamo ricombiniamo
loro, quello che stiamo facendo

209
00:10:06,680 --> 00:10:11,110
è sostanzialmente raddoppiando la
dimensioni delle matrici più piccole.

210
00:10:11,110 --> 00:10:14,260
Abbiamo un po 'di un elemento
array che abbiamo effettivamente

211
00:10:14,260 --> 00:10:16,290
combinarle in due array di elementi.

212
00:10:16,290 --> 00:10:18,590
E poi prendiamo quelli
due array di elementi

213
00:10:18,590 --> 00:10:21,890
e combinarli per creare
quattro matrici elemento, e così via,

214
00:10:21,890 --> 00:10:26,130
e così via, e così via, fino a che
avere un singolo elemento dell'array n.

215
00:10:26,130 --> 00:10:29,910
>> Ma quanti raddoppi
ci vuole per arrivare a n?

216
00:10:29,910 --> 00:10:31,460
Ripensate all'esempio rubrica telefonica.

217
00:10:31,460 --> 00:10:34,490
Quante volte dobbiamo strappare
la rubrica telefonica a metà, come molti altri

218
00:10:34,490 --> 00:10:38,370
volte dobbiamo strappare la rubrica telefonica
a metà, se la dimensione della rubrica

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

220
00:10:39,680 --> 00:10:41,960
C'è solo uno, giusto?

221
00:10:41,960 --> 00:10:45,360
>> Quindi c'è una sorta di
elemento logaritmica qui.

222
00:10:45,360 --> 00:10:48,590
Ma abbiamo anche ancora almeno
guarda tutti gli elementi n.

223
00:10:48,590 --> 00:10:53,860
Così, nel peggiore dei casi,
merge sort viene eseguito in log n n.

224
00:10:53,860 --> 00:10:56,160
Dobbiamo guardare
tutti gli n elementi,

225
00:10:56,160 --> 00:11:02,915
e dobbiamo combinarli
insieme a log n rampe di scale.

226
00:11:02,915 --> 00:11:05,290
Nel migliore dei casi,
la matrice è perfettamente ordinato.

227
00:11:05,290 --> 00:11:06,300
È fantastico.

228
00:11:06,300 --> 00:11:09,980
Ma in base all'algoritmo che abbiamo qui,
dobbiamo ancora suddividere e ricombinare.

229
00:11:09,980 --> 00:11:13,290
Anche se in questo caso, la
ricombinazione è una specie di inefficace.

230
00:11:13,290 --> 00:11:14,720
Non è necessario.

231
00:11:14,720 --> 00:11:17,580
Ma abbiamo ancora attraversiamo
l'intero processo comunque.

232
00:11:17,580 --> 00:11:21,290
>> Quindi nel caso migliore
e, nel caso peggiore,

233
00:11:21,290 --> 00:11:24,970
questo algoritmo viene eseguito in n log n tempo.

234
00:11:24,970 --> 00:11:29,130
Merge sort è sicuramente un po 'più complicato
rispetto agli altri algoritmi di ordinamento principali

235
00:11:29,130 --> 00:11:33,470
abbiamo parlato di CS50 ma è
sostanzialmente più potente.

236
00:11:33,470 --> 00:11:35,400
>> E così se mai trovare
occasione di bisogno

237
00:11:35,400 --> 00:11:38,480
o usarlo per ordinare un
grande insieme di dati, ottenendo

238
00:11:38,480 --> 00:11:41,940
la testa intorno all'idea di ricorsione
sta per essere davvero potente.

239
00:11:41,940 --> 00:11:45,270
E sta andando a rendere la vostra
programmi davvero molto più efficiente

240
00:11:45,270 --> 00:11:48,700
utilizzando merge sort contro qualsiasi altra cosa.

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

242
00:11:49,640 --> 00:11:51,970
Questo è CS50.

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