1
00:00:00,000 --> 00:00:04,419
>> [Prehrávanie hudby]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, takže zlúčenie
sort je ďalším algoritmus

4
00:00:08,460 --> 00:00:11,200
že môžeme použiť vyriešiť
prvky poľa.

5
00:00:11,200 --> 00:00:14,480
Ale ako uvidíme, je to dostal
veľmi zásadný rozdiel

6
00:00:14,480 --> 00:00:17,850
z výber druhu, bublina
triediť a insertion sort

7
00:00:17,850 --> 00:00:20,280
ktoré robia to naozaj celkom šikovný.

8
00:00:20,280 --> 00:00:24,290
>> Základnou myšlienkou zlúčenie
triedenie je triediť menších polí

9
00:00:24,290 --> 00:00:27,430
a potom spojiť tieto polia
dohromady, alebo zlúčiť them--

10
00:00:27,430 --> 00:00:31,440
od tejto doby name-- v zoradení poradí.

11
00:00:31,440 --> 00:00:34,230
Spôsob, akým merge sort robí
to je využitím nástroja

12
00:00:34,230 --> 00:00:37,290
zvanej rekurzia, čo je to, čo
budeme hovoriť o skoro,

13
00:00:37,290 --> 00:00:39,720
ale my sme naozaj hovoril o doteraz.

14
00:00:39,720 --> 00:00:43,010
>> Tu je základná myšlienka zlúčenie druhu.

15
00:00:43,010 --> 00:00:46,320
Triediť ľavú polovicu poľa,
za predpokladu, že n je väčšie ako 1.

16
00:00:46,320 --> 00:00:49,980
A čo mám na mysli, keď hovorím
za predpokladu, že n je väčšie ako 1, je,

17
00:00:49,980 --> 00:00:53,970
Myslím, že sa zhodneme na tom, že ak pole
iba sa skladá z jedného prvku,

18
00:00:53,970 --> 00:00:54,680
je to triediť.

19
00:00:54,680 --> 00:00:56,560
Nemáme skutočne potrebujú
urobiť čokoľvek, aby to.

20
00:00:56,560 --> 00:00:58,059
Môžeme len vyhlásiť, že majú byť triedené.

21
00:00:58,059 --> 00:01:00,110
Je to len jeden prvok.

22
00:01:00,110 --> 00:01:03,610
>> Takže pseudocode, opäť, je
zoradiť ľavej polovici poľa,

23
00:01:03,610 --> 00:01:08,590
potom triediť pravú polovicu poľa,
potom zlúčiť dve polovice dohromady.

24
00:01:08,590 --> 00:01:11,040
Teraz už by ste mali byť
myslenia, je to len trochu

25
00:01:11,040 --> 00:01:14,080
Znie to, ako by si odkladali the--
nie ste naozaj robiť nič.

26
00:01:14,080 --> 00:01:16,330
Hovoríš, že triediť ľavý
polovici, triediť pravú polovicu,

27
00:01:16,330 --> 00:01:19,335
ale ty nehovoríš
me, ako to robíte.

28
00:01:19,335 --> 00:01:22,220
>> Ale pamätajte si, že kým
pole je jeden element,

29
00:01:22,220 --> 00:01:23,705
môžeme prehlásiť, že triediť.

30
00:01:23,705 --> 00:01:25,330
Potom sa môžeme len spojiť dohromady.

31
00:01:25,330 --> 00:01:27,788
A to je vlastne
Základnou myšlienkou zlúčenie druhu,

32
00:01:27,788 --> 00:01:31,150
je rozobrať to tak, že
vaše pole má veľkosť jedného.

33
00:01:31,150 --> 00:01:33,430
A potom znova odtiaľ.

34
00:01:33,430 --> 00:01:35,910
>> Merge sort je určite
komplikovaný algoritmus.

35
00:01:35,910 --> 00:01:38,210
A je to tiež trochu
zložité predstaviť.

36
00:01:38,210 --> 00:01:41,870
Takže dúfajme, vizualizácia, ktoré som
tu vám pomôže sledovať spolu.

37
00:01:41,870 --> 00:01:45,640
A budem snažiť čo najlepšie rozprávať veci
a pokračovať cez to trochu viac

38
00:01:45,640 --> 00:01:49,180
pomalšie ako tie ostatné
len dúfajme, že si hlavu

39
00:01:49,180 --> 00:01:51,800
okolo myšlienok zlúčenie druhu.

40
00:01:51,800 --> 00:01:54,680
>> Takže máme rovnaké pole ako The
ďalšie triedenie algoritmus videá

41
00:01:54,680 --> 00:01:57,120
ak ste videli them--
Array šiestich prvok.

42
00:01:57,120 --> 00:02:02,110
A naše pseudokód kód tu je trochu
ľavá polovica, triediť pravú polovicu,

43
00:02:02,110 --> 00:02:03,890
spojiť obe polovice k sebe.

44
00:02:03,890 --> 00:02:09,770
Takže poďme sa tento veľmi tmavo tehlovo červená
poľa a triediť ľavú polovicu.

45
00:02:09,770 --> 00:02:13,380
>> Takže v súčasnej dobe, ideme
ignorovať veci na pravej strane.

46
00:02:13,380 --> 00:02:15,740
Je to tam, ale my sme
nie na ešte tomto kroku.

47
00:02:15,740 --> 00:02:18,220
Nie sme na radiť
pravá polovica poľa.

48
00:02:18,220 --> 00:02:21,037
Sme na druhu Na ľavej
polovica poľa.

49
00:02:21,037 --> 00:02:22,870
A len kvôli
z toho, že trochu viac

50
00:02:22,870 --> 00:02:26,480
jasné, takže môžem odkázať
k tomu, čo sme na krok,

51
00:02:26,480 --> 00:02:29,800
Budem prepnutie
Farba tohto nastavená na oranžovú.

52
00:02:29,800 --> 00:02:33,190
Teraz sme stále hovoril o
To isté ľavú polovicu pôvodného poľa.

53
00:02:33,190 --> 00:02:38,520
Ale ja dúfam, že tým, že je schopný
odkazujú na farby rôznych položiek,

54
00:02:38,520 --> 00:02:40,900
to bude robiť to o niečo viac
jasné, čo sa tu deje.

55
00:02:40,900 --> 00:02:43,270
>> OK, takže teraz máme
Tri element poľa.

56
00:02:43,270 --> 00:02:46,420
Ako môžeme radiť ľavej polovici tohto
poľa, čo je stále ešte tento krok?

57
00:02:46,420 --> 00:02:49,400
Snažíme sa vyriešiť ľavú
polovica tehlovo červená array--

58
00:02:49,400 --> 00:02:52,410
ľavá polovica z nich
Ja som teraz vo farbe oranžovej.

59
00:02:52,410 --> 00:02:54,840
>> No, mohli by sme skúsiť a
tento proces opakovať.

60
00:02:54,840 --> 00:02:56,756
Takže sme stále v
Uprostred sa snaží vyriešiť

61
00:02:56,756 --> 00:02:58,700
ľavá polovica celé pole.

62
00:02:58,700 --> 00:03:00,450
Ľavá polovica
pole, ja som jednoducho ísť

63
00:03:00,450 --> 00:03:03,910
svojvoľne rozhodnúť, že ľavá polovica
bude menšia, než v pravej polovici,

64
00:03:03,910 --> 00:03:06,550
preto, že sa to stane
sa skladá z troch častí.

65
00:03:06,550 --> 00:03:11,260
>> A tak budem hovoriť, že
Ľavá polovica ľavej polovici Array

66
00:03:11,260 --> 00:03:14,050
je len element päť.

67
00:03:14,050 --> 00:03:18,360
Five, ktorý je jediný prvok
poľa, vieme, ako to vyriešiť.

68
00:03:18,360 --> 00:03:21,615
A tak sa päť zoradené.

69
00:03:21,615 --> 00:03:22,990
Sme len tak určil.

70
00:03:22,990 --> 00:03:24,890
Je to jediný Prvok poľa.

71
00:03:24,890 --> 00:03:29,015
>> Preto sme teraz triedi
Ľavá polovica ľavého half--

72
00:03:29,015 --> 00:03:33,190
alebo skôr sme triedi
Ľavá polovica oranžové.

73
00:03:33,190 --> 00:03:37,970
Takže teraz, aby sa ešte kompletné
Celkovým array ľavá polovica,

74
00:03:37,970 --> 00:03:43,481
musíme radiť pravú polovicu
v oranžovej, alebo tejto veci.

75
00:03:43,481 --> 00:03:44,230
Ako to urobíme?

76
00:03:44,230 --> 00:03:45,930
No, máme dve element poľa.

77
00:03:45,930 --> 00:03:50,470
Takže môžeme radiť ľavú polovicu
matice, ktorý je dva.

78
00:03:50,470 --> 00:03:52,090
Two je jeden element.

79
00:03:52,090 --> 00:03:55,890
Takže je to radené v predvolenom nastavení.
Potom môžeme radiť pravú polovicu

80
00:03:55,890 --> 00:03:58,530
tej časti poľa, ten.

81
00:03:58,530 --> 00:04:00,210
To je tak nejako v predvolenom nastavení.

82
00:04:00,210 --> 00:04:03,610
>> Toto je teraz prvýkrát
sme dosiahli zlúčenie krok.

83
00:04:03,610 --> 00:04:06,135
Dokončili sme, hoci
Teraz trochu vnorené down--

84
00:04:06,135 --> 00:04:08,420
a to je druh chúlostivé
tá vec s rekurzia je,

85
00:04:08,420 --> 00:04:10,930
budete potrebovať, aby vaše
hlavu o tom, kde sme.

86
00:04:10,930 --> 00:04:15,560
Takže sme nejako vľavo
polovica oranžovej časti.

87
00:04:15,560 --> 00:04:21,280
>> A teraz, sme uprostred triedenie
pravá polovica oranžovej časti.

88
00:04:21,280 --> 00:04:25,320
A v tomto procese, sme
teraz asi byť na kroku

89
00:04:25,320 --> 00:04:27,850
spojiť obe polovice k sebe.

90
00:04:27,850 --> 00:04:31,700
Keď sa pozrieme na dve polovice
matice, vidíme, dva a jeden.

91
00:04:31,700 --> 00:04:33,880
Ktorý prvok je menšie?

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

93
00:04:35,160 --> 00:04:36,760
>> Potom ktorý element je menšie?

94
00:04:36,760 --> 00:04:38,300
No, je to dva alebo nič.

95
00:04:38,300 --> 00:04:39,910
Takže je to dva.

96
00:04:39,910 --> 00:04:43,690
Takže teraz, len preto, aby znovu rámu
kde sme v kontexte,

97
00:04:43,690 --> 00:04:48,230
sme triedila
Ľavá polovica oranžová

98
00:04:48,230 --> 00:04:49,886
a pravá polovica pôvodu.

99
00:04:49,886 --> 00:04:52,510
Viem, že som zmenil farby
znova, ale to je, kde sme boli.

100
00:04:52,510 --> 00:04:54,676
A dôvod, prečo som to urobil
je preto, že je tento proces

101
00:04:54,676 --> 00:04:57,870
bude ďalej, iterácie dole.

102
00:04:57,870 --> 00:05:00,500
Sme radené ľavý
polovicu bývalého oranžové

103
00:05:00,500 --> 00:05:02,590
a pravá polovica bývalej oranžovej.

104
00:05:02,590 --> 00:05:05,620
>> Teraz musíme spojiť tých,
dve polovice dohromady taky.

105
00:05:05,620 --> 00:05:07,730
To je krok, že sme na.

106
00:05:07,730 --> 00:05:11,440
Takže sme do úvahy všetky
prvky, ktoré sú teraz zelené,

107
00:05:11,440 --> 00:05:12,972
ľavú polovicu pôvodného poľa.

108
00:05:12,972 --> 00:05:14,680
A my sme zlúčiť tie
pomocou rovnakého procesu

109
00:05:14,680 --> 00:05:18,660
sme pre zlúčenie dvoch
a pred chvíľou.

110
00:05:18,660 --> 00:05:23,080
>> Ľavá polovica, najmenší
prvok v ľavej polovici je päť.

111
00:05:23,080 --> 00:05:25,620
Najmenší element na
pravá polovica je jeden.

112
00:05:25,620 --> 00:05:27,370
Ktorý z nich je menšia?

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

114
00:05:29,260 --> 00:05:32,250
>> Najmenší element na
ľavá polovica je päť.

115
00:05:32,250 --> 00:05:35,540
Najmenší element na
pravá polovica sú dva.

116
00:05:35,540 --> 00:05:36,970
Aký je najmenší?

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

118
00:05:38,160 --> 00:05:41,540
A potom konečne päť a
nič, môžeme povedať, päť.

119
00:05:41,540 --> 00:05:43,935
>> OK, takže veľký obrázok, poďme
pauzu na sekundu

120
00:05:43,935 --> 00:05:46,080
a zistiť, kde sme.

121
00:05:46,080 --> 00:05:48,580
Ak by sme začali od
samého začiatku, my

122
00:05:48,580 --> 00:05:51,640
teraz dokončená
celkovej pole len

123
00:05:51,640 --> 00:05:53,810
jeden krok zo pseudokódu kódu tu.

124
00:05:53,810 --> 00:05:56,645
Máme triedila
Ľavá polovica poľa.

125
00:05:56,645 --> 00:05:59,490
>> Pripomeňme, že pôvodný
Poradie bolo päť, dva, jedna.

126
00:05:59,490 --> 00:06:02,570
Tým, že ide v tomto procese
a hniezdenia dole a opakovanie,

127
00:06:02,570 --> 00:06:05,990
pokračovanie rozbiť problém
na menšie a menšie časti,

128
00:06:05,990 --> 00:06:09,670
sme teraz dokončili
kroku jeden z pseudocode

129
00:06:09,670 --> 00:06:13,940
pre celú štartové pole.

130
00:06:13,940 --> 00:06:16,670
Máme radené jeho ľavú polovicu.

131
00:06:16,670 --> 00:06:18,670
>> Takže teraz poďme tam zmrznúť.

132
00:06:18,670 --> 00:06:23,087
A teraz poďme zoradiť právo
polovicu pôvodného poľa.

133
00:06:23,087 --> 00:06:25,670
A budeme robiť, že
prechádza rovnaký iteratívny

134
00:06:25,670 --> 00:06:30,630
Proces lámanie veci dole
a potom ich zlúči dohromady.

135
00:06:30,630 --> 00:06:34,290
>> Takže ľavá polovica
červenej, alebo ľavá polovica

136
00:06:34,290 --> 00:06:38,830
z pravej polovice originálu
pole, budem hovoriť, je tri.

137
00:06:38,830 --> 00:06:40,312
Opäť platí, že som tu konzistentné.

138
00:06:40,312 --> 00:06:42,020
Ak máte nepárny
počet prvkov to,

139
00:06:42,020 --> 00:06:44,478
nie je naozaj jedno, či
urobíte vľavo jedna menšia

140
00:06:44,478 --> 00:06:45,620
alebo právo jedna menšia.

141
00:06:45,620 --> 00:06:49,230
>> Dôležité je, že vždy, keď vás
narazíte na tento problém v implementácii

142
00:06:49,230 --> 00:06:51,422
zlúčenie, musíte byť konzistentné.

143
00:06:51,422 --> 00:06:53,505
Buď Vždy musíte
urobiť ľavej strane menší

144
00:06:53,505 --> 00:06:55,421
alebo vždy potrebné, aby sa
pravá strana menšie.

145
00:06:55,421 --> 00:06:57,720
Tu som si vybral, aby sa vždy
aby sa ľavá strana menšie

146
00:06:57,720 --> 00:07:04,380
keď moje pole, alebo my
sub-pole, je nepárne veľkosti.

147
00:07:04,380 --> 00:07:07,420
>> Tri je jediný prvok,
a tak to je triedený.

148
00:07:07,420 --> 00:07:10,860
Sme zadlužuje tento predpoklad
v celom nášho procesu tak ďaleko.

149
00:07:10,860 --> 00:07:15,020
Takže teraz poďme zoradiť právo
polovica pravú polovicu,

150
00:07:15,020 --> 00:07:18,210
alebo pravá polovica červenej.

151
00:07:18,210 --> 00:07:20,390
>> Opäť platí, že musíme rozdeliť tento nadol.

152
00:07:20,390 --> 00:07:21,910
To nie je jediný prvok poľa.

153
00:07:21,910 --> 00:07:23,970
Nemôžeme vyhlásiť ju za radené.

154
00:07:23,970 --> 00:07:27,060
A tak ako prvý, ideme
triediť ľavú polovicu.

155
00:07:27,060 --> 00:07:31,620
>> Ľavá polovica je jediný prvok,
tak je to niečo v predvolenom nastavení.

156
00:07:31,620 --> 00:07:34,840
Potom budeme triediť právo
polovica, čo je jeden element.

157
00:07:34,840 --> 00:07:41,250
Je radené v predvolenom nastavení. A teraz,
môžeme spojiť tieto dve dohromady.

158
00:07:41,250 --> 00:07:45,820
Štyri je menšie, a
potom šiestich je menšia.

159
00:07:45,820 --> 00:07:48,870
>> Opäť platí, že to, čo sme urobili v tomto bode?

160
00:07:48,870 --> 00:07:52,512
Sme radené ľavý
polovica pravú polovicu.

161
00:07:52,512 --> 00:07:54,720
Alebo sa vracia k pôvodnému
farby, ktoré tam boli,

162
00:07:54,720 --> 00:07:57,875
sme radené ľavý
polovica mäkšie červené.

163
00:07:57,875 --> 00:08:00,416
To bolo pôvodne tmavá tehla
červenej a teraz je to mäkšie červená,

164
00:08:00,416 --> 00:08:02,350
alebo to bol mäkšie červené.

165
00:08:02,350 --> 00:08:05,145
>> A potom sme sa triedi
Pravá polovica mäkšie červené.

166
00:08:05,145 --> 00:08:08,270
A teraz, no, oni sú zase zelená, len
preto, že sme prechádza procesom.

167
00:08:08,270 --> 00:08:10,720
A my musíme opakovať
to znova a znova.

168
00:08:10,720 --> 00:08:14,695
>> Takže teraz sa môžeme spojiť tie,
dve polovice dohromady.

169
00:08:14,695 --> 00:08:15,820
A to je to, čo robíme tu.

170
00:08:15,820 --> 00:08:17,653
Takže čiernou linkou len
rozdelil ľavú polovicu

171
00:08:17,653 --> 00:08:19,690
a pravá polovica tohto druhu dielu.

172
00:08:19,690 --> 00:08:24,310
>> Porovnávame najmenšiu hodnotu
na ľavej strane array--

173
00:08:24,310 --> 00:08:26,710
alebo prepáčte, najmenší
Hodnota ľavej polovice

174
00:08:26,710 --> 00:08:30,790
na najmenšie hodnoty práva
polovicou a zistíte, že tri je menšia.

175
00:08:30,790 --> 00:08:32,530
A teraz trochu optimalizácia, že jo?

176
00:08:32,530 --> 00:08:35,175
Tam je vlastne nič,
vľavo na ľavej strane.

177
00:08:35,175 --> 00:08:37,440
>> Neexistuje nič, čo zvyšné
na ľavej strane,

178
00:08:37,440 --> 00:08:40,877
takže môžeme efektívne
Len move-- môžeme prehlásiť

179
00:08:40,877 --> 00:08:42,960
to ostatné je vlastne
triedené a jednoducho ho pripichnúť

180
00:08:42,960 --> 00:08:45,126
ďalej, pretože tam nič
iný porovnať proti.

181
00:08:45,126 --> 00:08:49,140
A my vieme, že na pravej strane
z pravej strany sa triedi.

182
00:08:49,140 --> 00:08:52,770
>> OK, tak teraz poďme opäť zmrzne a
zistiť, kde sme v príbehu.

183
00:08:52,770 --> 00:08:56,120
V celkovom poli,
čo sme dosiahnuť?

184
00:08:56,120 --> 00:08:58,790
My sme vlastne dosiahnuť
Teraz kroky jedno a krok dve.

185
00:08:58,790 --> 00:09:03,300
Vyriešili sme ľavú polovicu, a
sme radené pravú polovicu.

186
00:09:03,300 --> 00:09:08,210
>> Takže teraz, všetko, čo zostáva, je pre nás
zlúčiť tieto dve polovice dohromady.

187
00:09:08,210 --> 00:09:11,670
Takže sme porovnať najnižšou hodnotou
prvok každej polovici poľa

188
00:09:11,670 --> 00:09:13,510
postupne a pokračovať.

189
00:09:13,510 --> 00:09:16,535
Jedným z nich je nižší ako tri, takže jeden ide.

190
00:09:16,535 --> 00:09:19,770
>> Dva je nižší ako tri, takže dvoma ide.

191
00:09:19,770 --> 00:09:22,740
Tri je menší ako 5, takže tromi ide.

192
00:09:22,740 --> 00:09:25,820
Štyri je menší ako 5, takže štyrmi ide.

193
00:09:25,820 --> 00:09:30,210
Potom piatich menší ako šesť,
a šesť je jediné, čo zostáva.

194
00:09:30,210 --> 00:09:31,820
>> Teraz viem, že to bolo veľa krokov.

195
00:09:31,820 --> 00:09:33,636
A my sme opustili veľa
pamäte v našej brázde.

196
00:09:33,636 --> 00:09:35,260
A to je to, čo tie šedé štvorce sú.

197
00:09:35,260 --> 00:09:40,540
A to asi pocit, že vzal
oveľa dlhšie, než insertion sort, bublina

198
00:09:40,540 --> 00:09:42,660
triedenie, alebo výber triedenie.

199
00:09:42,660 --> 00:09:45,330
>> Ale v skutočnosti, pretože
Mnoho z týchto procesov

200
00:09:45,330 --> 00:09:48,260
sa dejú v rovnakom time--
čo je niečo, čo sme to znova,

201
00:09:48,260 --> 00:09:51,100
hovorí o tom, kedy hovoríme o
rekurzia v budúcnosti video--

202
00:09:51,100 --> 00:09:53,799
tento algoritmus vlastne
jasne je zásadne

203
00:09:53,799 --> 00:09:55,590
iný ako čokoľvek,
sme nevideli

204
00:09:55,590 --> 00:09:58,820
ale je tiež významne
efektívnejšie.

205
00:09:58,820 --> 00:09:59,532
>> Prečo tomu tak je?

206
00:09:59,532 --> 00:10:01,240
No, v najhoršom
scenár, máme

207
00:10:01,240 --> 00:10:04,830
rozdeliť n prvkov up
a potom sa zlučujú.

208
00:10:04,830 --> 00:10:06,680
Ale keď sme sa rekombinovať
je to, čo robíme

209
00:10:06,680 --> 00:10:11,110
je v podstate zdvojnásobiť
veľkosť menších polí.

210
00:10:11,110 --> 00:10:14,260
Máme veľa jedného prvku
polí, že sme účinne

211
00:10:14,260 --> 00:10:16,290
spojiť do dvoch prvkov poľa.

212
00:10:16,290 --> 00:10:18,590
A potom sme sa tým,
dve prvok poľa

213
00:10:18,590 --> 00:10:21,890
a spojiť ich dohromady do
štyri prvok poľa, a tak ďalej,

214
00:10:21,890 --> 00:10:26,130
a tak ďalej, a tak ďalej, až kým sme
mať jediný n prvok poľa.

215
00:10:26,130 --> 00:10:29,910
>> Ale koľko zdvojenie
trvá, než sa dostať na n?

216
00:10:29,910 --> 00:10:31,460
Spomeňte si na príklad telefónneho zoznamu.

217
00:10:31,460 --> 00:10:34,490
Koľkokrát musíme roztrhať
telefónny zoznam na polovicu, koľko ďalších

218
00:10:34,490 --> 00:10:38,370
časy máme k roztrhnutiu telefónneho zoznamu
na polovicu, ak je veľkosť telefónneho zoznamu

219
00:10:38,370 --> 00:10:39,680
zdvojnásobil?

220
00:10:39,680 --> 00:10:41,960
Je tu len jeden, nie?

221
00:10:41,960 --> 00:10:45,360
>> Takže tam je nejaký druh
logaritmické prvkom je tu.

222
00:10:45,360 --> 00:10:48,590
Ale tiež sme ešte najmenej
pozrieť sa na všetky z n prvkov.

223
00:10:48,590 --> 00:10:53,860
Takže v najhoršom prípade,
merge sort beží v n log n.

224
00:10:53,860 --> 00:10:56,160
Musíme sa pozrieť na
všetky z n elementy,

225
00:10:56,160 --> 00:11:02,915
a musíme kombinovať
spolu v protokole n sád krokov.

226
00:11:02,915 --> 00:11:05,290
V najlepšom prípade,
pole je dokonale zoradené.

227
00:11:05,290 --> 00:11:06,300
To je skvelé.

228
00:11:06,300 --> 00:11:09,980
Ale na základe algoritmu tu máme,
stále musíme rozdeliť a rekombinácie.

229
00:11:09,980 --> 00:11:13,290
Aj keď v tomto prípade,
rekombinantným je druh neefektívne.

230
00:11:13,290 --> 00:11:14,720
To nie je nutné.

231
00:11:14,720 --> 00:11:17,580
Ale my stále prejsť
celý proces tak ako tak.

232
00:11:17,580 --> 00:11:21,290
>> Takže v najlepšom prípade
a v najhoršom prípade,

233
00:11:21,290 --> 00:11:24,970
Tento algoritmus beží v n log n času.

234
00:11:24,970 --> 00:11:29,130
Merge sort je určite niečo ťažšie
než ostatné hlavné triedenie algoritmy

235
00:11:29,130 --> 00:11:33,470
sme hovorili o CS50, ale je
podstatne silnejší.

236
00:11:33,470 --> 00:11:35,400
>> A tak ak ste niekedy nájsť
príležitosť ju potrebujú

237
00:11:35,400 --> 00:11:38,480
alebo ju použiť zoradiť
veľký súbor dát, ako sa

238
00:11:38,480 --> 00:11:41,940
vaša hlava okolo myšlienky na rekurzia
bude naozaj silný.

239
00:11:41,940 --> 00:11:45,270
A to bude, aby vaše
Programy naozaj oveľa efektívnejšie

240
00:11:45,270 --> 00:11:48,700
pomocou merge sort oproti čokoľvek iného.

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

242
00:11:49,640 --> 00:11:51,970
To je CS50.

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