1
00:00:00,000 --> 00:00:04,419
>> [Speel van musiek]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, so 'n samesmelting
soort is nog 'n algoritme

4
00:00:08,460 --> 00:00:11,200
wat ons kan gebruik om uit te sorteer
die elemente van 'n skikking.

5
00:00:11,200 --> 00:00:14,480
Maar soos ons sal sien, is dit 'n
baie fundamentele verskil

6
00:00:14,480 --> 00:00:17,850
van seleksie soort, borrel
soort, en voeg soort

7
00:00:17,850 --> 00:00:20,280
wat maak dit regtig mooi slim.

8
00:00:20,280 --> 00:00:24,290
>> Die basiese idee agter merge
sorteer is om kleiner skikkings sorteer

9
00:00:24,290 --> 00:00:27,430
en kombineer dan diegene skikkings
saam te smelt of them--

10
00:00:27,430 --> 00:00:31,440
vandaar die name-- in gesorteerde volgorde.

11
00:00:31,440 --> 00:00:34,230
Die manier waarop saamsmelt soort doen
dit is deur gebruik te maak 'n instrument

12
00:00:34,230 --> 00:00:37,290
genoem rekursie, en dit is wat
ons gaan om te praat oor gou,

13
00:00:37,290 --> 00:00:39,720
maar ons het nie regtig gepraat oor nie.

14
00:00:39,720 --> 00:00:43,010
>> Hier is die basiese idee agter merge soort.

15
00:00:43,010 --> 00:00:46,320
Sorteer die linker helfte van die skikking,
veronderstelling N groter as 1.

16
00:00:46,320 --> 00:00:49,980
En wat ek bedoel as ek sê
veronderstelling N groter as 1 is,

17
00:00:49,980 --> 00:00:53,970
Ek dink ons ​​kan saamstem dat indien 'n skikking
net bestaan ​​uit 'n enkele element,

18
00:00:53,970 --> 00:00:54,680
dit is gesorteer.

19
00:00:54,680 --> 00:00:56,560
Ons het nie eintlik nodig
om iets te doen om dit te.

20
00:00:56,560 --> 00:00:58,059
Ons kan net verklaar dat dit word gesorteer.

21
00:00:58,059 --> 00:01:00,110
Dit is net 'n enkele element.

22
00:01:00,110 --> 00:01:03,610
>> So die pseudokode, weer, is
sorteer die linker helfte van die skikking,

23
00:01:03,610 --> 00:01:08,590
dan sorteer die regter helfte van die skikking,
dan saam te smelt die twee helftes saam.

24
00:01:08,590 --> 00:01:11,040
Nou, al wat jy kan wees
dink, is dit soort van net

25
00:01:11,040 --> 00:01:14,080
klink soos jy om af the--
jy nie eintlik enigiets doen.

26
00:01:14,080 --> 00:01:16,330
Jy sê sorteer links
helfte, sorteer die regter helfte,

27
00:01:16,330 --> 00:01:19,335
Maar jy is nie vertel
my hoe jy doen dit.

28
00:01:19,335 --> 00:01:22,220
>> Maar onthou dat so lank as wat
'n skikking is 'n enkele element,

29
00:01:22,220 --> 00:01:23,705
kan ons dit verklaar gesorteer.

30
00:01:23,705 --> 00:01:25,330
Dan kan ons net kombineer hulle saam.

31
00:01:25,330 --> 00:01:27,788
En dit is eintlik die
fundamentele idee agter merge soort,

32
00:01:27,788 --> 00:01:31,150
is om dit af te breek sodat
jou skikkings is van die grootte een.

33
00:01:31,150 --> 00:01:33,430
En dan moet jy weer op te bou van daar af.

34
00:01:33,430 --> 00:01:35,910
>> Merge soort is beslis
'n ingewikkelde algoritme.

35
00:01:35,910 --> 00:01:38,210
En dit is ook 'n bietjie
ingewikkeld om te visualiseer.

36
00:01:38,210 --> 00:01:41,870
So hopelik die visualisering dat ek
hier sal help jy volg saam.

37
00:01:41,870 --> 00:01:45,640
En ek sal my bes probeer om dinge te vertel
en gaan deur middel van hierdie 'n bietjie meer

38
00:01:45,640 --> 00:01:49,180
stadiger as die ander kinders
net om hopelik kry jou kop

39
00:01:49,180 --> 00:01:51,800
rondom die idees agter merge soort.

40
00:01:51,800 --> 00:01:54,680
>> So ons het dieselfde verskeidenheid as die
ander sorteer algoritme videos

41
00:01:54,680 --> 00:01:57,120
As jy gesien het them--
'n ses element skikking.

42
00:01:57,120 --> 00:02:02,110
En ons pseudokode kode hier is 'n soort
die linker helfte, sorteer die regter helfte,

43
00:02:02,110 --> 00:02:03,890
saamsmelt die twee helftes saam.

44
00:02:03,890 --> 00:02:09,770
So laat neem hierdie baie donker baksteenrooi
skikking en sorteer die linkerkant helfte van dit.

45
00:02:09,770 --> 00:02:13,380
>> So vir die oomblik, ons gaan
om die dinge op die regte ignoreer.

46
00:02:13,380 --> 00:02:15,740
Dit is daar, maar ons is
nie nog daardie stap.

47
00:02:15,740 --> 00:02:18,220
Ons is nie op die soort
regter helfte van die skikking.

48
00:02:18,220 --> 00:02:21,037
Ons is op sorteer links
helfte van die skikking.

49
00:02:21,037 --> 00:02:22,870
En net ter wille
dat dit 'n bietjie meer

50
00:02:22,870 --> 00:02:26,480
duidelik, sodat ek kan verwys
na wat stap ons op,

51
00:02:26,480 --> 00:02:29,800
Ek gaan die skakel
kleur van hierdie stel na oranje.

52
00:02:29,800 --> 00:02:33,190
Nou, ons is nog steeds praat oor die
dieselfde links die helfte van die oorspronklike skikking.

53
00:02:33,190 --> 00:02:38,520
Maar ek hoop dat deur dit kan
verwys na die kleure van die verskillende items,

54
00:02:38,520 --> 00:02:40,900
dit sal dit 'n bietjie meer te maak
duidelik wat gaan hier aan.

55
00:02:40,900 --> 00:02:43,270
>> OK, so nou het ons 'n
drie element skikking.

56
00:02:43,270 --> 00:02:46,420
Hoe weet ons sorteer die linker helfte van hierdie
skikking, wat nog steeds hierdie stap?

57
00:02:46,420 --> 00:02:49,400
Ons probeer om die linker sorteer
helfte van die baksteen rooi array--

58
00:02:49,400 --> 00:02:52,410
die linker helfte van wat
Ek het nou gekleurde oranje.

59
00:02:52,410 --> 00:02:54,840
>> Wel, kan ons probeer
herhaal hierdie proses.

60
00:02:54,840 --> 00:02:56,756
So ons is nog steeds in die
middel van probeer om te sorteer

61
00:02:56,756 --> 00:02:58,700
die linker helfte van die volle reeks.

62
00:02:58,700 --> 00:03:00,450
Die linker helfte van die
skikking, is ek net gaan

63
00:03:00,450 --> 00:03:03,910
om arbitrêr besluit dat die linker helfte
kleiner as die regter helfte sal wees,

64
00:03:03,910 --> 00:03:06,550
want dit gebeur met
bestaan ​​uit drie elemente.

65
00:03:06,550 --> 00:03:11,260
>> En so ek gaan om te sê dat die
linkerhelfte van die linker helfte van die reeks

66
00:03:11,260 --> 00:03:14,050
is net die element vyf.

67
00:03:14,050 --> 00:03:18,360
Vyf, wat 'n enkele element
skikking, ons weet hoe om dit te sorteer.

68
00:03:18,360 --> 00:03:21,615
En so vyf gesorteer.

69
00:03:21,615 --> 00:03:22,990
Ons is net gaan om te verklaar dat.

70
00:03:22,990 --> 00:03:24,890
Dit is 'n enkele element skikking.

71
00:03:24,890 --> 00:03:29,015
>> Dus het ons nou gesorteer die
linkerhelfte van die linker half--

72
00:03:29,015 --> 00:03:33,190
of eerder, ons het gesorteer die
links die helfte van die oranje.

73
00:03:33,190 --> 00:03:37,970
So nou, ten einde steeds volledige
links die helfte van die algehele array se

74
00:03:37,970 --> 00:03:43,481
ons nodig het om die regter helfte sorteer
van die oranje, of hierdie dinge.

75
00:03:43,481 --> 00:03:44,230
Hoe kan ons dit doen?

76
00:03:44,230 --> 00:03:45,930
Wel, ons het 'n twee element skikking.

77
00:03:45,930 --> 00:03:50,470
So kan ons die weg helfte sorteer
van die skikking, wat twee.

78
00:03:50,470 --> 00:03:52,090
Twee is 'n enkele element.

79
00:03:52,090 --> 00:03:55,890
So dit gesorteer is by verstek.
Dan kan ons die regter helfte sorteer

80
00:03:55,890 --> 00:03:58,530
van daardie gedeelte van die skikking, die een.

81
00:03:58,530 --> 00:04:00,210
Dit is soort van by verstek.

82
00:04:00,210 --> 00:04:03,610
>> Dit is nou vir die eerste keer
Ons het 'n merge stap bereik.

83
00:04:03,610 --> 00:04:06,135
Ons voltooi het, hoewel
ons nou soort van geneste down--

84
00:04:06,135 --> 00:04:08,420
en dit is soort van die moeilike
ding met rekursie is,

85
00:04:08,420 --> 00:04:10,930
wat jy nodig het om jou te hou
kop oor waar ons is.

86
00:04:10,930 --> 00:04:15,560
Dus het ons soort van links
helfte van die oranje gedeelte.

87
00:04:15,560 --> 00:04:21,280
>> En nou, ons is in die middel van die sortering
die regter helfte van die oranje gedeelte.

88
00:04:21,280 --> 00:04:25,320
En in die proses, ons is
nou tot op die stap,

89
00:04:25,320 --> 00:04:27,850
saamsmelt die twee helftes saam.

90
00:04:27,850 --> 00:04:31,700
As ons kyk na die twee helftes
van die skikking, sien ons twee en een.

91
00:04:31,700 --> 00:04:33,880
Watter element is kleiner?

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

93
00:04:35,160 --> 00:04:36,760
>> Dan watter element is kleiner?

94
00:04:36,760 --> 00:04:38,300
Wel, dit is twee of niks.

95
00:04:38,300 --> 00:04:39,910
So dit is twee.

96
00:04:39,910 --> 00:04:43,690
So nou, net om weer te raam
waar ons is in konteks,

97
00:04:43,690 --> 00:04:48,230
ons het gesorteer die
links die helfte van die oranje

98
00:04:48,230 --> 00:04:49,886
en die regter helfte van die oorsprong.

99
00:04:49,886 --> 00:04:52,510
Ek weet ek het die kleure verander
weer, maar dit is waar ons was.

100
00:04:52,510 --> 00:04:54,676
En die rede waarom ek dit gedoen het
is omdat hierdie proses is

101
00:04:54,676 --> 00:04:57,870
gaan om aan te hou, iterating af.

102
00:04:57,870 --> 00:05:00,500
Ons het die linker gesorteer
helfte van die voormalige oranje

103
00:05:00,500 --> 00:05:02,590
en die regter helfte van die voormalige oranje.

104
00:05:02,590 --> 00:05:05,620
>> Nou moet ons diegene saamsmelt
twee helftes saam ook.

105
00:05:05,620 --> 00:05:07,730
Dit is die stap ons op.

106
00:05:07,730 --> 00:05:11,440
So ons kyk na al die
elemente wat nou groen,

107
00:05:11,440 --> 00:05:12,972
die linker helfte van die oorspronklike skikking.

108
00:05:12,972 --> 00:05:14,680
En ons saamsmelt diegene
gebruik dieselfde proses

109
00:05:14,680 --> 00:05:18,660
ons gedoen het vir die samesmelting van twee
en een net 'n oomblik gelede.

110
00:05:18,660 --> 00:05:23,080
>> Die linker helfte, die kleinste
element op die linker helfte is vyf.

111
00:05:23,080 --> 00:05:25,620
Die kleinste element op
die regter helfte is een.

112
00:05:25,620 --> 00:05:27,370
Watter een van dié is kleiner?

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

114
00:05:29,260 --> 00:05:32,250
>> Die kleinste element op
die linker helfte is vyf.

115
00:05:32,250 --> 00:05:35,540
Die kleinste element op
die regter helfte is twee.

116
00:05:35,540 --> 00:05:36,970
Wat is die kleinste?

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

118
00:05:38,160 --> 00:05:41,540
En dan laastens vyf en
niks kan ons sê vyf.

119
00:05:41,540 --> 00:05:43,935
>> OK, so groot prentjie, laat
neem 'n breek vir 'n tweede

120
00:05:43,935 --> 00:05:46,080
en uit te vind waar ons is.

121
00:05:46,080 --> 00:05:48,580
As ons begin van
die begin af, ons

122
00:05:48,580 --> 00:05:51,640
het nou voltooi
die algehele array net

123
00:05:51,640 --> 00:05:53,810
een stap van die pseudokode kode hier.

124
00:05:53,810 --> 00:05:56,645
Ons het die gesorteer
linkerhelfte van die skikking.

125
00:05:56,645 --> 00:05:59,490
>> Onthou dat die oorspronklike
Om was vyf, twee, een.

126
00:05:59,490 --> 00:06:02,570
Deur te gaan deur die proses
en nes af en herhaal,

127
00:06:02,570 --> 00:06:05,990
voortgaan om die probleem te breek
af in kleiner en kleiner dele,

128
00:06:05,990 --> 00:06:09,670
ons het nou voltooi
Stap een van die pseudokode

129
00:06:09,670 --> 00:06:13,940
vir die hele beginspan skikking.

130
00:06:13,940 --> 00:06:16,670
Ons het sy linker helfte gesorteer.

131
00:06:16,670 --> 00:06:18,670
>> So nou, laat ons daar vries.

132
00:06:18,670 --> 00:06:23,087
En nou, laat se sorteer die regte
die helfte van die oorspronklike skikking.

133
00:06:23,087 --> 00:06:25,670
En ons gaan om dit te doen deur
gaan deur dieselfde iteratiewe

134
00:06:25,670 --> 00:06:30,630
proses van die breek dinge af
en dan saamsmelt hulle saam.

135
00:06:30,630 --> 00:06:34,290
>> So die linker helfte van die
rooi, of die linker helfte

136
00:06:34,290 --> 00:06:38,830
van die reg helfte van die oorspronklike
skikking, ek gaan om te sê, is die drie.

137
00:06:38,830 --> 00:06:40,312
Weereens, ek hier is konsekwent.

138
00:06:40,312 --> 00:06:42,020
As jy 'n vreemde
aantal elemente, is dit

139
00:06:42,020 --> 00:06:44,478
maak nie regtig saak of
jy links een kleiner te maak

140
00:06:44,478 --> 00:06:45,620
of die regte een kleiner.

141
00:06:45,620 --> 00:06:49,230
>> Wat belangrik is, is dat wanneer jy
teëkom hierdie probleem in die uitvoering van

142
00:06:49,230 --> 00:06:51,422
'n saamsmelt, moet jy konsekwent te wees.

143
00:06:51,422 --> 00:06:53,505
Jy óf altyd nodig om
maak 'n linkerkant kleiner

144
00:06:53,505 --> 00:06:55,421
of altyd nodig om te maak
die regterkant kleiner.

145
00:06:55,421 --> 00:06:57,720
Hier het ek gekies om altyd
maak die linkerkant kleiner

146
00:06:57,720 --> 00:07:04,380
toe my skikking, of my
sub-skikking, is van 'n vreemde grootte.

147
00:07:04,380 --> 00:07:07,420
>> Drie is 'n enkele element,
en so is dit gesorteer.

148
00:07:07,420 --> 00:07:10,860
Ons het hierdie aanname aged
ons hele proses so ver.

149
00:07:10,860 --> 00:07:15,020
So nou, laat ons sorteer die regte
helfte van die regter helfte,

150
00:07:15,020 --> 00:07:18,210
of die regter helfte van die rooi.

151
00:07:18,210 --> 00:07:20,390
>> Weereens, moet ons dit verdeel af.

152
00:07:20,390 --> 00:07:21,910
Dit is nie 'n enkele element skikking.

153
00:07:21,910 --> 00:07:23,970
Ons kan nie verkondig nie gesorteer.

154
00:07:23,970 --> 00:07:27,060
En so die eerste, ons gaan
aan die linkerkant half sorteer.

155
00:07:27,060 --> 00:07:31,620
>> Die linker helfte is 'n enkele element,
so dit is soort van by verstek.

156
00:07:31,620 --> 00:07:34,840
Dan gaan ons die regte soort
helfte, wat is 'n enkele element.

157
00:07:34,840 --> 00:07:41,250
Dit is gesorteer by verstek. En nou,
ons kan die twee saam te smelt.

158
00:07:41,250 --> 00:07:45,820
Vier is kleiner, en
dan ses kleiner is.

159
00:07:45,820 --> 00:07:48,870
>> Weereens, wat het ons gedoen op hierdie punt?

160
00:07:48,870 --> 00:07:52,512
Ons het die linker gesorteer
helfte van die regter helfte.

161
00:07:52,512 --> 00:07:54,720
Of gaan terug na die oorspronklike
kleure wat daar was,

162
00:07:54,720 --> 00:07:57,875
ons het die linker gesorteer
helfte van die sagter rooi.

163
00:07:57,875 --> 00:08:00,416
Dit was oorspronklik 'n donker baksteen
rooi en nou is dit 'n sagter rooi,

164
00:08:00,416 --> 00:08:02,350
of was dit 'n sagter rooi.

165
00:08:02,350 --> 00:08:05,145
>> En dan het ons gesorteer die
regter helfte van die sagter rooi.

166
00:08:05,145 --> 00:08:08,270
Nou, goed, hulle is groen weer, net
want ons gaan deur 'n proses.

167
00:08:08,270 --> 00:08:10,720
En ons moet herhaal
dit oor en oor.

168
00:08:10,720 --> 00:08:14,695
>> So nou kan ons saam te smelt diegene
twee helftes saam.

169
00:08:14,695 --> 00:08:15,820
En dit is wat ons hier doen.

170
00:08:15,820 --> 00:08:17,653
So die swart lyn net
verdeel die linker helfte

171
00:08:17,653 --> 00:08:19,690
en die regter helfte van hierdie soort deel.

172
00:08:19,690 --> 00:08:24,310
>> Ons vergelyk die kleinste waarde
aan die linkerkant van die array--

173
00:08:24,310 --> 00:08:26,710
of verskoon my, die kleinste
waarde van die linker helfte

174
00:08:26,710 --> 00:08:30,790
die kleinste waarde van die reg
helfte en vind dat drie kleiner is.

175
00:08:30,790 --> 00:08:32,530
En nou 'n bietjie van 'n optimalisering, reg?

176
00:08:32,530 --> 00:08:35,175
Daar is eintlik niks
links op die linkerkant.

177
00:08:35,175 --> 00:08:37,440
>> Daar is niks wat oorbly
aan die linkerkant,

178
00:08:37,440 --> 00:08:40,877
sodat ons kan doeltreffend
net move-- kan ons verklaar

179
00:08:40,877 --> 00:08:42,960
die res van dit is eintlik
gesorteer en net ryg dit

180
00:08:42,960 --> 00:08:45,126
op, want daar is niks
anders vergelyk.

181
00:08:45,126 --> 00:08:49,140
En ons weet dat die regterkant
van die regterkant gesorteer.

182
00:08:49,140 --> 00:08:52,770
>> OK, so nou kom ons weer vries en
uit te vind waar ons is in die storie.

183
00:08:52,770 --> 00:08:56,120
In die algehele skikking,
wat het ons bereik?

184
00:08:56,120 --> 00:08:58,790
Ons het eintlik bereik
nou gee een en stap twee.

185
00:08:58,790 --> 00:09:03,300
Ons gesorteer links helfte, en
Ons gesorteer die regter helfte.

186
00:09:03,300 --> 00:09:08,210
>> So nou, al wat oorbly is vir ons
om die twee helftes saam te smelt.

187
00:09:08,210 --> 00:09:11,670
So ons vergelyk met die laagste gewaardeer
element van elke helfte van die skikking

188
00:09:11,670 --> 00:09:13,510
op sy beurt en voort te gaan.

189
00:09:13,510 --> 00:09:16,535
Een daarvan is minder as drie, so een gaan.

190
00:09:16,535 --> 00:09:19,770
>> Twee is minder as drie, so twee gaan.

191
00:09:19,770 --> 00:09:22,740
Drie is minder as 5, so drie gaan.

192
00:09:22,740 --> 00:09:25,820
Vier is minder as 5, so vier gaan.

193
00:09:25,820 --> 00:09:30,210
Dan is vyf minder as ses,
en ses is al wat oorbly.

194
00:09:30,210 --> 00:09:31,820
>> Nou, ek weet, dit was 'n baie stappe.

195
00:09:31,820 --> 00:09:33,636
En ons het 'n baie gelaat
geheue in ons wakker.

196
00:09:33,636 --> 00:09:35,260
En dit is wat die grys vierkante is.

197
00:09:35,260 --> 00:09:40,540
En dit is waarskynlik so gevoel het 'n
baie langer as invoeging soort, borrel

198
00:09:40,540 --> 00:09:42,660
soort, of seleksie soort.

199
00:09:42,660 --> 00:09:45,330
>> Maar eintlik, want 'n
Baie van hierdie prosesse

200
00:09:45,330 --> 00:09:48,260
gebeur op dieselfde time--
dit is iets wat ons sal weer,

201
00:09:48,260 --> 00:09:51,100
praat oor wanneer ons praat oor
rekursie in 'n toekomstige video--

202
00:09:51,100 --> 00:09:53,799
hierdie algoritme eintlik
duidelik is fundamenteel

203
00:09:53,799 --> 00:09:55,590
anders as enigiets
ons vantevore gesien

204
00:09:55,590 --> 00:09:58,820
maar is ook aansienlik
meer doeltreffend.

205
00:09:58,820 --> 00:09:59,532
>> Hoekom is dit?

206
00:09:59,532 --> 00:10:01,240
Wel, in die ergste
geval scenario, ons het

207
00:10:01,240 --> 00:10:04,830
om n elemente verdeel
en dan herkombineer hulle.

208
00:10:04,830 --> 00:10:06,680
Maar toe ons herkombineer
hulle wat ons doen

209
00:10:06,680 --> 00:10:11,110
is basies die verdubbeling van die
grootte van die kleiner skikkings.

210
00:10:11,110 --> 00:10:14,260
Ons het 'n klomp van die een element
skikkings dat ons effektief

211
00:10:14,260 --> 00:10:16,290
kombineer in twee element skikkings.

212
00:10:16,290 --> 00:10:18,590
En dan neem ons daardie
twee skikkings element

213
00:10:18,590 --> 00:10:21,890
en kombineer hulle saam in
vier element skikkings, en so aan,

214
00:10:21,890 --> 00:10:26,130
en so aan, en so aan, totdat ons
'n enkele N element skikking.

215
00:10:26,130 --> 00:10:29,910
>> Maar hoeveel verdubbelingen
neem dit om n te kry?

216
00:10:29,910 --> 00:10:31,460
Dink terug aan die telefoon boek voorbeeld.

217
00:10:31,460 --> 00:10:34,490
Hoeveel keer het ons om te skeur
die telefoon boek in die helfte, hoeveel meer

218
00:10:34,490 --> 00:10:38,370
keer doen ons die telefoon boek skeur
in die helfte, as die grootte van die telefoon boek

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

220
00:10:39,680 --> 00:10:41,960
Daar is net een, reg?

221
00:10:41,960 --> 00:10:45,360
>> So is daar 'n soort van
logaritmiese element hier.

222
00:10:45,360 --> 00:10:48,590
Maar ons het ook nog moet ten minste
kyk na al die elemente N.

223
00:10:48,590 --> 00:10:53,860
So in die ergste geval scenario,
saamsmelt soort loop in n log n.

224
00:10:53,860 --> 00:10:56,160
Ons het om te kyk na
al die elemente N,

225
00:10:56,160 --> 00:11:02,915
en ons het om hulle te kombineer
saam in log N stelle stappe.

226
00:11:02,915 --> 00:11:05,290
In die beste geval,
die skikking is perfek gesorteer.

227
00:11:05,290 --> 00:11:06,300
Dit is 'n groot.

228
00:11:06,300 --> 00:11:09,980
Maar op grond van die algoritme wat ons hier,
ons het nog te verdeel en verbind.

229
00:11:09,980 --> 00:11:13,290
Hoewel in hierdie geval, die
recombining is soort van ondoeltreffend.

230
00:11:13,290 --> 00:11:14,720
Dit is nie nodig nie.

231
00:11:14,720 --> 00:11:17,580
Maar ons het nog gaan deur
die hele proses in elk geval.

232
00:11:17,580 --> 00:11:21,290
>> So in die beste geval
en in die ergste geval,

233
00:11:21,290 --> 00:11:24,970
hierdie algoritme loop in n log N tyd.

234
00:11:24,970 --> 00:11:29,130
Merge soort is beslis 'n bietjie moeiliker
as die ander belangrikste sorteringsalgoritmes

235
00:11:29,130 --> 00:11:33,470
Ons het gepraat oor CS50, maar is
aansienlik meer kragtig.

236
00:11:33,470 --> 00:11:35,400
>> En so as jy ooit vind
geleentheid om dit nodig

237
00:11:35,400 --> 00:11:38,480
of om dit te gebruik om 'n soort
groot data stel, om

238
00:11:38,480 --> 00:11:41,940
jou kop rondom die idee van rekursie
gaan werklik kragtig te wees.

239
00:11:41,940 --> 00:11:45,270
En dit gaan om jou
programme regtig veel meer doeltreffend

240
00:11:45,270 --> 00:11:48,700
gebruik van saamsmelt soort versus enigiets anders.

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

242
00:11:49,640 --> 00:11:51,970
Dit is CS50.

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