1
00:00:00,000 --> 00:00:04,419
>> [Muziek]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, dus een fusie
soort is nog een ander algoritme

4
00:00:08,460 --> 00:00:11,200
die we kunnen gebruiken om uit te zoeken
de elementen van een array.

5
00:00:11,200 --> 00:00:14,480
Maar zoals we zullen zien, het heeft een
zeer fundamenteel verschil

6
00:00:14,480 --> 00:00:17,850
uit selectie sorteren, bubble
sorteren en insertion sort

7
00:00:17,850 --> 00:00:20,280
die het echt mooi slim.

8
00:00:20,280 --> 00:00:24,290
>> Het basisidee achter merge
sorteren is om kleinere arrays te sorteren

9
00:00:24,290 --> 00:00:27,430
en combineer dan die arrays
samen, of samenvoegen them--

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

11
00:00:31,440 --> 00:00:34,230
De manier waarop die fuseren soort doet
dit is door gebruik te maken van een hulpmiddel

12
00:00:34,230 --> 00:00:37,290
genaamd recursie, dat is wat
we gaan praten over snel,

13
00:00:37,290 --> 00:00:39,720
maar we hebben niet echt gesproken over nog.

14
00:00:39,720 --> 00:00:43,010
>> Hier is het basisidee achter merge soort.

15
00:00:43,010 --> 00:00:46,320
Sorteer de linkerhelft van de array,
uitgaande van n groter is dan 1.

16
00:00:46,320 --> 00:00:49,980
En wat ik bedoel als ik zeg
uitgaande van n groter dan 1 is,

17
00:00:49,980 --> 00:00:53,970
Ik denk dat we het erover eens dat als een array
slechts bestaat uit een enkel element,

18
00:00:53,970 --> 00:00:54,680
het is opgelost.

19
00:00:54,680 --> 00:00:56,560
We niet echt nodig
om iets te doen aan het.

20
00:00:56,560 --> 00:00:58,059
We kunnen alleen maar verklaren het te sorteren.

21
00:00:58,059 --> 00:01:00,110
Het is slechts een enkel element.

22
00:01:00,110 --> 00:01:03,610
>> Dus de pseudocode, opnieuw, is
sorteren de linkerhelft van de array,

23
00:01:03,610 --> 00:01:08,590
vervolgens sorteert de rechter helft van de array,
dan samenvoegen van de twee helften aan elkaar.

24
00:01:08,590 --> 00:01:11,040
Nu, al u misschien wel
denken, het vriendelijk van enkel

25
00:01:11,040 --> 00:01:14,080
klinkt alsof je uit te stellen the--
je bent niet echt iets te doen.

26
00:01:14,080 --> 00:01:16,330
Je zegt sorteren links
helft, sorteert de rechter helft,

27
00:01:16,330 --> 00:01:19,335
maar je bent niet vertellen
me hoe je het doet het.

28
00:01:19,335 --> 00:01:22,220
>> Maar vergeet niet dat, zolang
een array is een enkel element,

29
00:01:22,220 --> 00:01:23,705
kunnen we verklaren het opgelost.

30
00:01:23,705 --> 00:01:25,330
Dan kunnen we net combineren ze samen.

31
00:01:25,330 --> 00:01:27,788
En dat is eigenlijk de
fundamentele idee achter merge sort,

32
00:01:27,788 --> 00:01:31,150
is om het af te breken, zodat
uw arrays zijn omvang een.

33
00:01:31,150 --> 00:01:33,430
En dan moet je weer op te bouwen vanaf daar.

34
00:01:33,430 --> 00:01:35,910
>> Merge sort is zeker
een ingewikkeld algoritme.

35
00:01:35,910 --> 00:01:38,210
En het is ook een beetje
gecompliceerd te visualiseren.

36
00:01:38,210 --> 00:01:41,870
Dus hopelijk, de visualisatie die ik
hier hebben zal je helpen volgen langs.

37
00:01:41,870 --> 00:01:45,640
En ik zal mijn best doen om dingen te vertellen
en verder door deze een beetje meer

38
00:01:45,640 --> 00:01:49,180
langzamer dan de anderen
alleen maar om hopelijk je hoofd

39
00:01:49,180 --> 00:01:51,800
rond de ideeën achter merge soort.

40
00:01:51,800 --> 00:01:54,680
>> Dus we hebben dezelfde array als de
andere sorteer-algoritme videos

41
00:01:54,680 --> 00:01:57,120
Als je hebt gezien them--
een zes-element array.

42
00:01:57,120 --> 00:02:02,110
En onze pseudocode code hier is een soort
de linker helft, sorteren van de rechter helft,

43
00:02:02,110 --> 00:02:03,890
samenvoegen van de twee helften aan elkaar.

44
00:02:03,890 --> 00:02:09,770
Dus laten we dit zeer donkere baksteen rood
array en sorteren van de linker helft van het.

45
00:02:09,770 --> 00:02:13,380
>> Dus voor het moment, we gaan
om de spullen op de juiste negeren.

46
00:02:13,380 --> 00:02:15,740
Het is er, maar we zijn
nog niet die stap.

47
00:02:15,740 --> 00:02:18,220
We zijn niet bij de soort
rechterhelft van de array.

48
00:02:18,220 --> 00:02:21,037
We zijn in een soort links
de helft van de array.

49
00:02:21,037 --> 00:02:22,870
En alleen omwille
van een beetje meer

50
00:02:22,870 --> 00:02:26,480
duidelijk, dus ik kan verwijzen
wat stap we op,

51
00:02:26,480 --> 00:02:29,800
Ik ga naar het schakelen
kleur van deze set naar oranje.

52
00:02:29,800 --> 00:02:33,190
Nu, we zijn nog steeds over de
Hetzelfde linkerhelft van de oorspronkelijke array.

53
00:02:33,190 --> 00:02:38,520
Maar ik hoop dat door te kunnen
verwijzen naar de kleuren van de verschillende items,

54
00:02:38,520 --> 00:02:40,900
het zal het een beetje meer te maken
duidelijk wat er aan de hand hier.

55
00:02:40,900 --> 00:02:43,270
>> OK, dus nu hebben we een
drie element array.

56
00:02:43,270 --> 00:02:46,420
Hoe kunnen we sorteren de linker helft van dit
matrix, die nog steeds deze stap?

57
00:02:46,420 --> 00:02:49,400
We proberen links te sorteren
de helft van de steenrode array--

58
00:02:49,400 --> 00:02:52,410
de linker helft
Ik heb nu oranje gekleurd.

59
00:02:52,410 --> 00:02:54,840
>> Nou, we kunnen proberen
herhaal dit proces.

60
00:02:54,840 --> 00:02:56,756
Dus we zijn nog steeds in de
midden van het proberen om te sorteren

61
00:02:56,756 --> 00:02:58,700
de linkerhelft van de volledige array.

62
00:02:58,700 --> 00:03:00,450
De linkerhelft van het
array, ik ben gewoon gaan

63
00:03:00,450 --> 00:03:03,910
willekeurig beslissen dat de linkerhelft
kleiner is dan de rechterhelft wordt,

64
00:03:03,910 --> 00:03:06,550
omdat dit gebeurt
bestaan ​​uit drie elementen.

65
00:03:06,550 --> 00:03:11,260
>> En dus ik ga om te zeggen dat de
linkerhelft van de linkerhelft de array

66
00:03:11,260 --> 00:03:14,050
is slechts het element vijf.

67
00:03:14,050 --> 00:03:18,360
Vijf, waarbij een enkel element
array, we weten hoe we het uitzoeken.

68
00:03:18,360 --> 00:03:21,615
En dus vijf wordt gesorteerd.

69
00:03:21,615 --> 00:03:22,990
We gaan gewoon om te verklaren dat.

70
00:03:22,990 --> 00:03:24,890
Het is een enkel element array.

71
00:03:24,890 --> 00:03:29,015
>> Dus we hebben nu naargelang de
linkerhelft van de linker half--

72
00:03:29,015 --> 00:03:33,190
of liever gezegd, we hebben naargelang de
linkerhelft van het oranje.

73
00:03:33,190 --> 00:03:37,970
Dus nu, met het oog op nog compleet
linkerhelft de totale array,

74
00:03:37,970 --> 00:03:43,481
we nodig hebben om de rechter helft afstand
van de oranje of dit spul.

75
00:03:43,481 --> 00:03:44,230
Hoe doen we dat?

76
00:03:44,230 --> 00:03:45,930
Nou, we hebben een twee-element array.

77
00:03:45,930 --> 00:03:50,470
Dus we kunnen de linker helft afstand
van de matrix, die twee.

78
00:03:50,470 --> 00:03:52,090
Twee een enkel element.

79
00:03:52,090 --> 00:03:55,890
Dus het is gesorteerd per default.
Dan kunnen we de juiste halve afstand

80
00:03:55,890 --> 00:03:58,530
van dat deel van de matrix, het.

81
00:03:58,530 --> 00:04:00,210
Dat is een soort van standaard.

82
00:04:00,210 --> 00:04:03,610
>> Dit is nu de eerste keer
we hebben een fusie stap bereikt.

83
00:04:03,610 --> 00:04:06,135
We hebben afgerond, hoewel
we nu soort geneste down--

84
00:04:06,135 --> 00:04:08,420
en dat is een soort van de lastige
ding met recursie is,

85
00:04:08,420 --> 00:04:10,930
je nodig hebt om je te houden
hoofd over waar we zijn.

86
00:04:10,930 --> 00:04:15,560
Dus we hebben een soort van links
de helft van de oranje gedeelte.

87
00:04:15,560 --> 00:04:21,280
>> En nu zijn we in het midden van het sorteren
de rechterhelft van de oranje gedeelte.

88
00:04:21,280 --> 00:04:25,320
En in dat proces zijn we
nu op het punt om op de stap,

89
00:04:25,320 --> 00:04:27,850
samenvoegen van de twee helften aan elkaar.

90
00:04:27,850 --> 00:04:31,700
Wanneer we kijken naar de twee helften
van de array, zien we twee en één.

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

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

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

94
00:04:36,760 --> 00:04:38,300
Nou, het is twee of niets.

95
00:04:38,300 --> 00:04:39,910
Dus het is twee.

96
00:04:39,910 --> 00:04:43,690
Dus nu, gewoon om opnieuw inlijsten
waar we zijn in context,

97
00:04:43,690 --> 00:04:48,230
we hebben naargelang de
linkerhelft van de oranje

98
00:04:48,230 --> 00:04:49,886
en de rechterhelft van de oorsprong.

99
00:04:49,886 --> 00:04:52,510
Ik weet dat ik de kleuren veranderd
weer, maar dat is waar we waren.

100
00:04:52,510 --> 00:04:54,676
En de reden dat ik dit deed
omdat dit proces

101
00:04:54,676 --> 00:04:57,870
gaat om door te gaan, iteratie beneden.

102
00:04:57,870 --> 00:05:00,500
We hebben de linker naargelang
de helft van de voormalige Oranje

103
00:05:00,500 --> 00:05:02,590
en de rechterhelft van de voormalige oranje.

104
00:05:02,590 --> 00:05:05,620
>> Nu moeten we die fuseren
twee helften elkaar ook.

105
00:05:05,620 --> 00:05:07,730
Dat is de stap die we nu op.

106
00:05:07,730 --> 00:05:11,440
Dus we rekening houden met alle van de
elementen die nu groen,

107
00:05:11,440 --> 00:05:12,972
de linkerhelft van de oorspronkelijke array.

108
00:05:12,972 --> 00:05:14,680
En we samenvoegen die
via hetzelfde proces

109
00:05:14,680 --> 00:05:18,660
we deden voor het samenvoegen van twee
en één slechts een moment geleden.

110
00:05:18,660 --> 00:05:23,080
>> De linkerhelft, de kleinste
element op de linkerhelft vijf.

111
00:05:23,080 --> 00:05:25,620
De kleinste element
de rechterhelft één.

112
00:05:25,620 --> 00:05:27,370
Welke van die kleiner?

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

114
00:05:29,260 --> 00:05:32,250
>> De kleinste element
de linkerhelft vijf.

115
00:05:32,250 --> 00:05:35,540
De kleinste element
de rechter helft is twee.

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

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

118
00:05:38,160 --> 00:05:41,540
En dan tot slot vijf en
niets, kunnen we zeggen vijf.

119
00:05:41,540 --> 00:05:43,935
>> OK, dus grote beeld, laten we
neem een ​​pauze voor een tweede

120
00:05:43,935 --> 00:05:46,080
en erachter te komen waar we zijn.

121
00:05:46,080 --> 00:05:48,580
Als we begonnen uit
het allereerste begin, we

122
00:05:48,580 --> 00:05:51,640
zijn nu ingevuld voor
de totale serie net

123
00:05:51,640 --> 00:05:53,810
een stap van de pseudo-code hier.

124
00:05:53,810 --> 00:05:56,645
We hebben naargelang de
linkerhelft van de array.

125
00:05:56,645 --> 00:05:59,490
>> Bedenk dat de oorspronkelijke
Om vijf, twee, één.

126
00:05:59,490 --> 00:06:02,570
Door te gaan door middel van dit proces
en nesten omlaag en herhalen,

127
00:06:02,570 --> 00:06:05,990
blijft het probleem breken
in kleinere en kleinere delen,

128
00:06:05,990 --> 00:06:09,670
we nu hebben afgerond
stap één van de pseudocode

129
00:06:09,670 --> 00:06:13,940
het gehele start array.

130
00:06:13,940 --> 00:06:16,670
We hebben haar linker helft opgelost.

131
00:06:16,670 --> 00:06:18,670
>> Dus laten we nu daar bevriezen.

132
00:06:18,670 --> 00:06:23,087
En laten we nu de juiste afstand
de helft van de oorspronkelijke array.

133
00:06:23,087 --> 00:06:25,670
En we gaan dat doen door
gaan door de dezelfde iteratieve

134
00:06:25,670 --> 00:06:30,630
proces van het breken van dingen naar beneden
en dan samen te voegen ze samen.

135
00:06:30,630 --> 00:06:34,290
>> Dus de linkerhelft van de
rood, of de linkerhelft

136
00:06:34,290 --> 00:06:38,830
van de rechterhelft van de oorspronkelijke
array, ik ga zeggen is drie.

137
00:06:38,830 --> 00:06:40,312
Nogmaals, ik ben om hier consequent.

138
00:06:40,312 --> 00:06:42,020
Als u een oneven
aantal elementen, dat

139
00:06:42,020 --> 00:06:44,478
niet echt uit of
je links een kleiner te maken

140
00:06:44,478 --> 00:06:45,620
of de juiste kleinere.

141
00:06:45,620 --> 00:06:49,230
>> Waar het om gaat is dat wanneer je
Dit probleem tegenkomen in geleidend

142
00:06:49,230 --> 00:06:51,422
een fusie, moet je consequent zijn.

143
00:06:51,422 --> 00:06:53,505
Of je altijd nodig hebt om
maak een linkerkant kleiner

144
00:06:53,505 --> 00:06:55,421
of altijd moet maken
rechts kleiner.

145
00:06:55,421 --> 00:06:57,720
Hier heb ik gekozen om altijd
maken de linkerzijde kleiner

146
00:06:57,720 --> 00:07:04,380
toen mijn array, of mijn
sub-array, is van een oneven grootte.

147
00:07:04,380 --> 00:07:07,420
>> Drie is een enkel element,
en dus het wordt gesorteerd.

148
00:07:07,420 --> 00:07:10,860
We hebben die veronderstelling leveraged
gedurende ons hele proces tot nu toe.

149
00:07:10,860 --> 00:07:15,020
Dus laten we nu de juiste afstand
de helft van de rechterhelft,

150
00:07:15,020 --> 00:07:18,210
of de rechterhelft van de rode.

151
00:07:18,210 --> 00:07:20,390
>> Nogmaals, we moeten deze split neer.

152
00:07:20,390 --> 00:07:21,910
Dit is geen enkel element array.

153
00:07:21,910 --> 00:07:23,970
We kunnen niet verklaren het opgelost.

154
00:07:23,970 --> 00:07:27,060
En dus eerst, we gaan
aan de linker helft afstand.

155
00:07:27,060 --> 00:07:31,620
>> De linkerhelft is een enkel element,
dus het is een soort van standaard.

156
00:07:31,620 --> 00:07:34,840
Dan gaan we naar de juiste soort
half, hetgeen een enkel element.

157
00:07:34,840 --> 00:07:41,250
Het is gesorteerd per default. En nu,
kunnen we die twee met elkaar fuseren.

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

159
00:07:45,820 --> 00:07:48,870
>> Nogmaals, wat hebben we gedaan op dit punt?

160
00:07:48,870 --> 00:07:52,512
We hebben de linker naargelang
de helft van de rechter helft.

161
00:07:52,512 --> 00:07:54,720
Of terug te gaan naar de oorspronkelijke
kleuren die er waren,

162
00:07:54,720 --> 00:07:57,875
we hebben de linker naargelang
de helft van de zachtere rood.

163
00:07:57,875 --> 00:08:00,416
Het was oorspronkelijk een donkere baksteen
rood en nu is het een zachter rood,

164
00:08:00,416 --> 00:08:02,350
of het een zachter rood.

165
00:08:02,350 --> 00:08:05,145
>> En dan hebben we naargelang de
rechterhelft van het zachtere rood.

166
00:08:05,145 --> 00:08:08,270
Nu goed, ze zijn weer groen, net
want we gaan door middel van een proces.

167
00:08:08,270 --> 00:08:10,720
En we moeten herhalen
dit over en voorbij.

168
00:08:10,720 --> 00:08:14,695
>> Dus nu kunnen we samenvoegen die
twee helften.

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

170
00:08:15,820 --> 00:08:17,653
Dus de zwarte lijn net
verdeelde de linkerhelft

171
00:08:17,653 --> 00:08:19,690
en de rechterhelft van deze soort onderdeel.

172
00:08:19,690 --> 00:08:24,310
>> We vergelijken de kleinste waarde
aan de linkerkant van de array--

173
00:08:24,310 --> 00:08:26,710
of neem me niet kwalijk, de kleinste
waarde van de linkerhelft

174
00:08:26,710 --> 00:08:30,790
de kleinste waarde van het recht
de helft en vind dat drie kleiner is.

175
00:08:30,790 --> 00:08:32,530
En nu een beetje een optimalisatie, toch?

176
00:08:32,530 --> 00:08:35,175
Er is eigenlijk niets
links op de linkerkant.

177
00:08:35,175 --> 00:08:37,440
>> Er is niets overgebleven
aan de linkerkant,

178
00:08:37,440 --> 00:08:40,877
dus we kunnen efficiënt
gewoon move-- kunnen we verklaren

179
00:08:40,877 --> 00:08:42,960
de rest van het is eigenlijk
gesorteerd en gewoon vastzetten

180
00:08:42,960 --> 00:08:45,126
op, want er is niets
anders om mee te vergelijken.

181
00:08:45,126 --> 00:08:49,140
En we weten dat de rechterzijde
de rechterzijde is gesorteerd.

182
00:08:49,140 --> 00:08:52,770
>> OK, dus laten we nu weer bevriezen en
erachter te komen waar we zijn in het verhaal.

183
00:08:52,770 --> 00:08:56,120
In de totale matrix,
wat hebben we bereikt?

184
00:08:56,120 --> 00:08:58,790
We hebben eigenlijk te bereiken
nu de stappen één en stap twee.

185
00:08:58,790 --> 00:09:03,300
We naargelang de linker helft, en
we naargelang de rechter helft.

186
00:09:03,300 --> 00:09:08,210
>> Dus nu, alles wat overblijft is voor ons
die twee helften samen te voegen.

187
00:09:08,210 --> 00:09:11,670
Dus we vergelijken met de laagste waarde
element van elke helft van de array

188
00:09:11,670 --> 00:09:13,510
beurt en gaan.

189
00:09:13,510 --> 00:09:16,535
Een daarvan is minder dan drie, dus men gaat.

190
00:09:16,535 --> 00:09:19,770
>> Twee minder dan drie, dus twee gaat.

191
00:09:19,770 --> 00:09:22,740
Drie minder dan 5, dus drie gaat.

192
00:09:22,740 --> 00:09:25,820
Vier minder dan 5, dus vier gaat.

193
00:09:25,820 --> 00:09:30,210
Dan is vijf minder dan zes,
en zes is dat alles blijft.

194
00:09:30,210 --> 00:09:31,820
>> Nu, ik weet het, dat was veel trappen.

195
00:09:31,820 --> 00:09:33,636
En we hebben veel links
geheugen in ons kielzog.

196
00:09:33,636 --> 00:09:35,260
En dat is wat die grijze vierkantjes zijn.

197
00:09:35,260 --> 00:09:40,540
En het waarschijnlijk voelde als die nam een
veel langer dan insertion sort, bel

198
00:09:40,540 --> 00:09:42,660
sort of selectie sorteren.

199
00:09:42,660 --> 00:09:45,330
>> Maar in feite, omdat
Veel van deze processen

200
00:09:45,330 --> 00:09:48,260
gebeuren op hetzelfde tijd--
dat is iets wat we zullen, nogmaals,

201
00:09:48,260 --> 00:09:51,100
praten over als we praten over
recursie in een toekomstige video--

202
00:09:51,100 --> 00:09:53,799
Dit algoritme eigenlijk
duidelijk is fundamenteel

203
00:09:53,799 --> 00:09:55,590
anders dan iets
we eerder hebben gezien

204
00:09:55,590 --> 00:09:58,820
maar ook significant
Meer efficiënt.

205
00:09:58,820 --> 00:09:59,532
>> Waarom is dat?

206
00:09:59,532 --> 00:10:01,240
Nou, in het ergste
geval, we

207
00:10:01,240 --> 00:10:04,830
n elementen splitsen
en vervolgens recombineren hen.

208
00:10:04,830 --> 00:10:06,680
Maar toen we recombineren
ze, wat we doen

209
00:10:06,680 --> 00:10:11,110
is in feite een verdubbeling van de
grootte van de kleinere matrices.

210
00:10:11,110 --> 00:10:14,260
We hebben een heleboel één element
arrays die we effectief

211
00:10:14,260 --> 00:10:16,290
combineren in twee elementen arrays.

212
00:10:16,290 --> 00:10:18,590
En dan nemen we die
twee element arrays

213
00:10:18,590 --> 00:10:21,890
en deze combineren in
vier element arrays, enzovoort,

214
00:10:21,890 --> 00:10:26,130
enzovoorts, enzovoorts, totdat we
een enkele n element array.

215
00:10:26,130 --> 00:10:29,910
>> Maar hoeveel verdubbelingen
duurt het om n te krijgen?

216
00:10:29,910 --> 00:10:31,460
Denk terug aan het telefoonboek voorbeeld.

217
00:10:31,460 --> 00:10:34,490
Hoe vaak hebben we te scheuren
het telefoonboek in de helft, hoeveel meer

218
00:10:34,490 --> 00:10:38,370
tijden moeten we het telefoonboek scheuren
in de helft, als de grootte van het telefoonboek

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

220
00:10:39,680 --> 00:10:41,960
Er is slechts één, toch?

221
00:10:41,960 --> 00:10:45,360
>> Dus er is een soort van
logaritmische element hier.

222
00:10:45,360 --> 00:10:48,590
Maar ook nog minstens
kijken naar alle van de n elementen.

223
00:10:48,590 --> 00:10:53,860
Dus in het ergste geval,
samenvoegen soort loopt in n log n.

224
00:10:53,860 --> 00:10:56,160
We moeten kijken naar
alle n elementen,

225
00:10:56,160 --> 00:11:02,915
en we hebben om ze te combineren
samen in log n sets van stappen.

226
00:11:02,915 --> 00:11:05,290
In het beste geval,
de array is perfect opgelost.

227
00:11:05,290 --> 00:11:06,300
Dat is geweldig.

228
00:11:06,300 --> 00:11:09,980
Maar gebaseerd op het algoritme wij hier
we hebben nog steeds te splitsen en recombineren.

229
00:11:09,980 --> 00:11:13,290
Hoewel in dit geval
recombineren is een soort van ineffectief.

230
00:11:13,290 --> 00:11:14,720
Het is niet noodzakelijk.

231
00:11:14,720 --> 00:11:17,580
Maar we nog steeds gaan door
het hele proces toch.

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

233
00:11:21,290 --> 00:11:24,970
dit algoritme draait in n log n tijd.

234
00:11:24,970 --> 00:11:29,130
Samenvoegen soort is zeker een beetje lastiger
dan de andere grote sortering algoritmen

235
00:11:29,130 --> 00:11:33,470
we hebben gesproken over CS50, maar is
aanzienlijk krachtiger.

236
00:11:33,470 --> 00:11:35,400
>> En dus als je ooit vinden
gelegenheid om het nodig hebben

237
00:11:35,400 --> 00:11:38,480
of te gebruiken om te sorteren
grote dataset, krijgen

238
00:11:38,480 --> 00:11:41,940
je hoofd rond het idee van recursie
gaat echt krachtig te zijn.

239
00:11:41,940 --> 00:11:45,270
En het gaat om uw
programma's echt veel efficiënter

240
00:11:45,270 --> 00:11:48,700
gebruik samenvoegen soort versus iets anders.

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

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

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