1
00:00:00,000 --> 00:00:04,419
>> [MUSIC SPILLE]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, så et flette
sort er nok en algoritme

4
00:00:08,460 --> 00:00:11,200
som vi kan bruke til å sortere ut
elementene i en matrise.

5
00:00:11,200 --> 00:00:14,480
Men som vi skal se, det har en
veldig fundamental forskjell

6
00:00:14,480 --> 00:00:17,850
fra utvalget sortere, boble
sortere og innsetting sort

7
00:00:17,850 --> 00:00:20,280
som gjør det egentlig ganske smart.

8
00:00:20,280 --> 00:00:24,290
>> Den grunnleggende ideen bak merge
sorter er å sortere mindre arrays

9
00:00:24,290 --> 00:00:27,430
og deretter kombinere disse arrays
sammen, eller flette them--

10
00:00:27,430 --> 00:00:31,440
derav name-- i sortert rekkefølge.

11
00:00:31,440 --> 00:00:34,230
Måten fusjonere slags gjør
dette er ved å utnytte et verktøy

12
00:00:34,230 --> 00:00:37,290
kalt rekursjon, som er hva
vi skal snakke om å bli snart,

13
00:00:37,290 --> 00:00:39,720
men vi har egentlig ikke snakket om ennå.

14
00:00:39,720 --> 00:00:43,010
>> Her er den grunnleggende ideen bak merge sort.

15
00:00:43,010 --> 00:00:46,320
Sortere venstre halvdel av tabellen,
forutsatt at n er større enn 1.

16
00:00:46,320 --> 00:00:49,980
Og hva jeg mener når jeg sier
forutsatt at n er større enn 1 er,

17
00:00:49,980 --> 00:00:53,970
Jeg tror vi kan være enige om at hvis en matrise
bare består av et enkelt element,

18
00:00:53,970 --> 00:00:54,680
det er sortert.

19
00:00:54,680 --> 00:00:56,560
Vi har ikke egentlig trenger
å gjøre noe til det.

20
00:00:56,560 --> 00:00:58,059
Vi kan bare erklære det som skal sorteres.

21
00:00:58,059 --> 00:01:00,110
Det er bare et enkelt element.

22
00:01:00,110 --> 00:01:03,610
>> Så pseudokode, igjen, er
sortere venstre halvdel av tabellen,

23
00:01:03,610 --> 00:01:08,590
deretter sortere høyre halvdel av tabellen,
deretter slå sammen de to halvdelene sammen.

24
00:01:08,590 --> 00:01:11,040
Nå, allerede kan du være
tenkning, den slags bare

25
00:01:11,040 --> 00:01:14,080
høres ut som du sette av the--
du faktisk ikke gjør noe.

26
00:01:14,080 --> 00:01:16,330
Du sier sortere venstre
halvparten, sortere høyre halvdel,

27
00:01:16,330 --> 00:01:19,335
men du er ikke å fortelle
meg hvordan du gjør det.

28
00:01:19,335 --> 00:01:22,220
>> Men husk at så lenge
en matrise er et enkelt element,

29
00:01:22,220 --> 00:01:23,705
vi kan erklære det sortert.

30
00:01:23,705 --> 00:01:25,330
Da kan vi bare kombinere dem sammen.

31
00:01:25,330 --> 00:01:27,788
Og det er faktisk den
Grunntanken bak merge sort,

32
00:01:27,788 --> 00:01:31,150
er å bryte det ned slik at
arrays er av størrelse en.

33
00:01:31,150 --> 00:01:33,430
Og så du gjenoppbygge derfra.

34
00:01:33,430 --> 00:01:35,910
>> Flett typen er definitivt
en komplisert algoritme.

35
00:01:35,910 --> 00:01:38,210
Og det er også litt
komplisert å visualisere.

36
00:01:38,210 --> 00:01:41,870
Så forhåpentligvis, visualisering som jeg
har her vil hjelpe deg å følge med.

37
00:01:41,870 --> 00:01:45,640
Og jeg skal prøve mitt beste for å fortelle ting
og gå gjennom dette litt mer

38
00:01:45,640 --> 00:01:49,180
saktere enn de andre
bare for å forhåpentligvis få hodet

39
00:01:49,180 --> 00:01:51,800
rundt ideene bak merge sort.

40
00:01:51,800 --> 00:01:54,680
>> Så vi har samme utvalg som
andre sorteringsalgoritme videoer

41
00:01:54,680 --> 00:01:57,120
Hvis du har sett them--
en seks element array.

42
00:01:57,120 --> 00:02:02,110
Og vår pseudokoden her er liksom
venstre halvdel, sortere høyre halvdel,

43
00:02:02,110 --> 00:02:03,890
fusjonere de to halvdelene sammen.

44
00:02:03,890 --> 00:02:09,770
Så la oss ta dette veldig mørk mursteinsrød
matrise og sortere igjen halvparten av det.

45
00:02:09,770 --> 00:02:13,380
>> Så for tiden, vi skal
å ignorere ting til høyre.

46
00:02:13,380 --> 00:02:15,740
Den er der, men vi er
ikke i det skrittet enda.

47
00:02:15,740 --> 00:02:18,220
Vi er ikke i form til
høyre halvdel av tabellen.

48
00:02:18,220 --> 00:02:21,037
Vi er på liksom venstre
halvparten av tabellen.

49
00:02:21,037 --> 00:02:22,870
Og bare for moro skyld
for å være litt mer

50
00:02:22,870 --> 00:02:26,480
klart, så jeg kan referere
til hva skritt vi er på,

51
00:02:26,480 --> 00:02:29,800
Jeg kommer til å slå
Fargen på dette settet til oransje.

52
00:02:29,800 --> 00:02:33,190
Nå er vi fremdeles snakker om
samme venstre halvdel av den opprinnelige matrisen.

53
00:02:33,190 --> 00:02:38,520
Men jeg håper at ved å være i stand til å
refererer til fargene på ulike elementer,

54
00:02:38,520 --> 00:02:40,900
det vil gjøre det litt mer
klart hva som skjer her.

55
00:02:40,900 --> 00:02:43,270
>> OK, så nå har vi en
tre-element array.

56
00:02:43,270 --> 00:02:46,420
Hvordan vi sorterer gjør den venstre halvdelen av dette
array, som fortsatt er dette trinnet?

57
00:02:46,420 --> 00:02:49,400
Vi prøver å sortere venstre
halvparten av mursteinsrød array--

58
00:02:49,400 --> 00:02:52,410
venstre hvorav halvparten
Jeg har nå farget oransje.

59
00:02:52,410 --> 00:02:54,840
>> Vel, vi kan prøve og
gjenta denne prosessen på nytt.

60
00:02:54,840 --> 00:02:56,756
Så vi er fortsatt i
midten av prøver å sortere

61
00:02:56,756 --> 00:02:58,700
den venstre halvdel av en fullstendig matrise.

62
00:02:58,700 --> 00:03:00,450
Den venstre halvdel av
matrise, jeg bare går

63
00:03:00,450 --> 00:03:03,910
å vilkårlig bestemme at den venstre halvdelen
vil være mindre enn den høyre halvdel,

64
00:03:03,910 --> 00:03:06,550
fordi dette skjer med
bestå av tre elementer.

65
00:03:06,550 --> 00:03:11,260
>> Og så kommer jeg til å si at
venstre halvdel av den venstre halvdel av matrisen

66
00:03:11,260 --> 00:03:14,050
er bare element fem.

67
00:03:14,050 --> 00:03:18,360
Five, som er en enkelt element
array, vet vi hvordan vi skal sortere det.

68
00:03:18,360 --> 00:03:21,615
Og så five blir sortert.

69
00:03:21,615 --> 00:03:22,990
Vi er bare nødt til å erklære det.

70
00:03:22,990 --> 00:03:24,890
Det er et enkelt element array.

71
00:03:24,890 --> 00:03:29,015
>> Så vi har nå sortert
venstre halvdel av venstre half--

72
00:03:29,015 --> 00:03:33,190
eller rettere sagt, har vi sortert
venstre halvdel av oransje.

73
00:03:33,190 --> 00:03:37,970
Så nå, for å fortsatt komplett
den samlede tabellens venstre halvdel,

74
00:03:37,970 --> 00:03:43,481
vi trenger å sortere høyre halvdel
av den oransje, eller slike ting.

75
00:03:43,481 --> 00:03:44,230
Hvordan gjør vi det?

76
00:03:44,230 --> 00:03:45,930
Vel, vi har en to element array.

77
00:03:45,930 --> 00:03:50,470
Så vi kan sortere venstre halvdel
i matrisen, som er to.

78
00:03:50,470 --> 00:03:52,090
To er et enkelt element.

79
00:03:52,090 --> 00:03:55,890
Så det er sortert etter standard.
Da kan vi sortere høyre halvdel

80
00:03:55,890 --> 00:03:58,530
av den del av matrisen, at en.

81
00:03:58,530 --> 00:04:00,210
Det er liksom som standard.

82
00:04:00,210 --> 00:04:03,610
>> Dette er nå første gang
vi har nådd et flette trinn.

83
00:04:03,610 --> 00:04:06,135
Vi har gjennomført, selv om
vi nå slags nestet down--

84
00:04:06,135 --> 00:04:08,420
og det er liksom den vanskelige
Saken med rekursjon er,

85
00:04:08,420 --> 00:04:10,930
du trenger for å holde
hodet om hvor vi er.

86
00:04:10,930 --> 00:04:15,560
Så vi har liksom venstre
halvparten av den oransje partiet.

87
00:04:15,560 --> 00:04:21,280
>> Og nå er vi i midten av sortering
den høyre halvdel av den oransje partiet.

88
00:04:21,280 --> 00:04:25,320
Og i denne prosessen, er vi
nå i ferd med å bli på trinnet,

89
00:04:25,320 --> 00:04:27,850
fusjonere de to halvdelene sammen.

90
00:04:27,850 --> 00:04:31,700
Når vi ser på de to halvdelene
av tabellen, ser vi to og en.

91
00:04:31,700 --> 00:04:33,880
Hvilket element er mindre?

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

93
00:04:35,160 --> 00:04:36,760
>> Så hvilket element er mindre?

94
00:04:36,760 --> 00:04:38,300
Vel, det er to eller ingenting.

95
00:04:38,300 --> 00:04:39,910
Så det er to.

96
00:04:39,910 --> 00:04:43,690
Så nå, bare for å igjen ramme
hvor vi er i sammenheng,

97
00:04:43,690 --> 00:04:48,230
Vi har sortert
venstre halvdel av oransje

98
00:04:48,230 --> 00:04:49,886
og den høyre halvdel av opprinnelsen.

99
00:04:49,886 --> 00:04:52,510
Jeg vet jeg har endret fargene
igjen, men det er der vi var.

100
00:04:52,510 --> 00:04:54,676
Og grunnen til at jeg gjorde dette
er fordi denne prosessen er

101
00:04:54,676 --> 00:04:57,870
kommer til å holde det gående, itera ned.

102
00:04:57,870 --> 00:05:00,500
Vi har sortert venstre
halvparten av det tidligere orange

103
00:05:00,500 --> 00:05:02,590
og den høyre halvparten av det tidligere orange.

104
00:05:02,590 --> 00:05:05,620
>> Nå trenger vi å fusjonere de
to halvdeler sammen også.

105
00:05:05,620 --> 00:05:07,730
Det er det trinnet vi er på.

106
00:05:07,730 --> 00:05:11,440
Så vi vurdere alle
elementer som nå er grønn,

107
00:05:11,440 --> 00:05:12,972
den venstre halvdel av den opprinnelige matrisen.

108
00:05:12,972 --> 00:05:14,680
Og vi slå sammen de
ved hjelp av den samme prosessen

109
00:05:14,680 --> 00:05:18,660
vi gjorde for å slå sammen to
og en bare et øyeblikk siden.

110
00:05:18,660 --> 00:05:23,080
>> Venstre halvdel, den minste
element på den venstre halvdelen er fem.

111
00:05:23,080 --> 00:05:25,620
Det minste elementet på
høyre halvdel er en.

112
00:05:25,620 --> 00:05:27,370
Hvilken av disse er mindre?

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

114
00:05:29,260 --> 00:05:32,250
>> Det minste elementet på
den venstre halvdelen er fem.

115
00:05:32,250 --> 00:05:35,540
Det minste elementet på
høyre halvdel er to.

116
00:05:35,540 --> 00:05:36,970
Hva er det minste?

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

118
00:05:38,160 --> 00:05:41,540
Og så til slutt fem og
ingenting, kan vi si fem.

119
00:05:41,540 --> 00:05:43,935
>> OK, så store bildet, la oss
ta en pause for en andre

120
00:05:43,935 --> 00:05:46,080
og finne ut hvor vi er.

121
00:05:46,080 --> 00:05:48,580
Hvis vi startet fra
helt i begynnelsen, vi

122
00:05:48,580 --> 00:05:51,640
har nå fullført for
den generelle matrisen bare

123
00:05:51,640 --> 00:05:53,810
ett trinn av pseudokode her.

124
00:05:53,810 --> 00:05:56,645
Vi har sortert
venstre halvdel av tabellen.

125
00:05:56,645 --> 00:05:59,490
>> Husk at den opprinnelige
For var fem, to, en.

126
00:05:59,490 --> 00:06:02,570
Ved å gå gjennom denne prosessen
og hekkende ned og gjenta,

127
00:06:02,570 --> 00:06:05,990
fortsetter å bryte problemet
ned i mindre og mindre deler,

128
00:06:05,990 --> 00:06:09,670
Vi har nå fullført
trinn en av pseudokode

129
00:06:09,670 --> 00:06:13,940
for hele start matrisen.

130
00:06:13,940 --> 00:06:16,670
Vi har sortert sin venstre halvdel.

131
00:06:16,670 --> 00:06:18,670
>> Så nå kan vi fryse der.

132
00:06:18,670 --> 00:06:23,087
Og nå la oss sortere riktig
halvparten av den opprinnelige matrisen.

133
00:06:23,087 --> 00:06:25,670
Og vi kommer til å gjøre det ved å
gå gjennom den samme iterativ

134
00:06:25,670 --> 00:06:30,630
Prosessen med å bryte ned ting
og deretter flette dem sammen.

135
00:06:30,630 --> 00:06:34,290
>> Så den venstre halvdel av
rød, eller venstre halvdel

136
00:06:34,290 --> 00:06:38,830
av den høyre halvparten av den opprinnelige
array, kommer jeg til å si er tre.

137
00:06:38,830 --> 00:06:40,312
Igjen, jeg er å være konsekvent her.

138
00:06:40,312 --> 00:06:42,020
Hvis du har en merkelig
antall elementer, det

139
00:06:42,020 --> 00:06:44,478
spiller ingen rolle om
du gjøre det igjen ett mindre

140
00:06:44,478 --> 00:06:45,620
eller den rette mindre.

141
00:06:45,620 --> 00:06:49,230
>> Det som betyr noe er at når du
opplever dette problemet i å gjennomføre

142
00:06:49,230 --> 00:06:51,422
en sammenslåing, må du være konsekvent.

143
00:06:51,422 --> 00:06:53,505
Du enten alltid trenger å
ta til venstre side mindre

144
00:06:53,505 --> 00:06:55,421
eller alltid trenger å gjøre
høyre side mindre.

145
00:06:55,421 --> 00:06:57,720
Her har jeg valgt å alltid
gjøre venstre side mindre

146
00:06:57,720 --> 00:07:04,380
da min array, eller min
deloppstilling, er av et odde størrelse.

147
00:07:04,380 --> 00:07:07,420
>> Tre er et enkelt element,
og så er det sortert.

148
00:07:07,420 --> 00:07:10,860
Vi drar nytte av at antakelsen
gjennom hele prosessen så langt.

149
00:07:10,860 --> 00:07:15,020
Så nå la oss sortere riktig
halvparten av den høyre halvdel,

150
00:07:15,020 --> 00:07:18,210
eller høyre halvdel av rødt.

151
00:07:18,210 --> 00:07:20,390
>> Igjen, vi trenger å dele dette ned.

152
00:07:20,390 --> 00:07:21,910
Dette er ikke et enkelt element array.

153
00:07:21,910 --> 00:07:23,970
Vi kan ikke erklære det sortert.

154
00:07:23,970 --> 00:07:27,060
Og så først skal vi
til å sortere den venstre halvdelen.

155
00:07:27,060 --> 00:07:31,620
>> Den venstre halvdel er et enkelt element,
så det er liksom som standard.

156
00:07:31,620 --> 00:07:34,840
Så skal vi til å sortere riktig
halvparten, noe som er et enkelt element.

157
00:07:34,840 --> 00:07:41,250
Den er sortert etter standard. Og nå,
vi kan slå sammen de to sammen.

158
00:07:41,250 --> 00:07:45,820
Fire er mindre, og
deretter seks er mindre.

159
00:07:45,820 --> 00:07:48,870
>> Igjen, hva har vi gjort på dette punktet?

160
00:07:48,870 --> 00:07:52,512
Vi har sortert venstre
halvparten av den høyre halvdel.

161
00:07:52,512 --> 00:07:54,720
Eller gå tilbake til den opprinnelige
farger som var der,

162
00:07:54,720 --> 00:07:57,875
vi har sortert venstre
halvparten av det mykere rødt.

163
00:07:57,875 --> 00:08:00,416
Det var opprinnelig en mørk murstein
rød og nå er det en mykere rød,

164
00:08:00,416 --> 00:08:02,350
eller det var en mykere rødt.

165
00:08:02,350 --> 00:08:05,145
>> Og så har vi sortert
høyre halvdel av mykere rødt.

166
00:08:05,145 --> 00:08:08,270
Nå, vel, de er grønne igjen, bare
fordi vi går gjennom en prosess.

167
00:08:08,270 --> 00:08:10,720
Og vi må gjenta
dette igjen og igjen.

168
00:08:10,720 --> 00:08:14,695
>> Så nå kan vi slå sammen de
to halvdeler sammen.

169
00:08:14,695 --> 00:08:15,820
Og det er det vi gjør her.

170
00:08:15,820 --> 00:08:17,653
Så den svarte linjen bare
delt den venstre halvdelen

171
00:08:17,653 --> 00:08:19,690
og høyre halvdel av denne typen delen.

172
00:08:19,690 --> 00:08:24,310
>> Vi sammenligner den minste verdien
på venstre side av array--

173
00:08:24,310 --> 00:08:26,710
eller unnskylde meg, den minste
Verdien av den venstre halvdel

174
00:08:26,710 --> 00:08:30,790
til den minste verdi av den rette
halvparten og finner ut at tre er mindre.

175
00:08:30,790 --> 00:08:32,530
Og nå litt av en optimalisering, ikke sant?

176
00:08:32,530 --> 00:08:35,175
Det er faktisk ingenting
igjen på venstre side.

177
00:08:35,175 --> 00:08:37,440
>> Det er ingenting igjen
på venstre side,

178
00:08:37,440 --> 00:08:40,877
så vi kan effektivt
bare move-- vi kan erklære

179
00:08:40,877 --> 00:08:42,960
resten av det faktisk
sortert og bare tack det

180
00:08:42,960 --> 00:08:45,126
på, fordi det er ingenting
annet å sammenligne mot.

181
00:08:45,126 --> 00:08:49,140
Og vi vet at høyre side
på høyre side er sortert.

182
00:08:49,140 --> 00:08:52,770
>> OK, så nå la oss fryse igjen og
finne ut hvor vi er i historien.

183
00:08:52,770 --> 00:08:56,120
I den generelle array,
hva har vi oppnådd?

184
00:08:56,120 --> 00:08:58,790
Vi har faktisk utrette
trinn nå en og trinn to.

185
00:08:58,790 --> 00:09:03,300
Vi sortert venstre halvdel, og
vi sortert høyre halvdel.

186
00:09:03,300 --> 00:09:08,210
>> Så nå, er for oss alt som gjenstår
å slå sammen de to halvdelene sammen.

187
00:09:08,210 --> 00:09:11,670
Så sammenligner vi den laveste verdsatt
element i hver halvdel av matrisen

188
00:09:11,670 --> 00:09:13,510
igjen og fortsette.

189
00:09:13,510 --> 00:09:16,535
Det ene er mindre enn tre, så man går.

190
00:09:16,535 --> 00:09:19,770
>> To er mindre enn tre, så to går.

191
00:09:19,770 --> 00:09:22,740
Tre er mindre enn 5, så tre går.

192
00:09:22,740 --> 00:09:25,820
Fire er mindre enn 5, så fire går.

193
00:09:25,820 --> 00:09:30,210
Da fem er mindre enn seks,
og seks er alt som gjenstår.

194
00:09:30,210 --> 00:09:31,820
>> Nå, jeg vet, det var mange av trinnene.

195
00:09:31,820 --> 00:09:33,636
Og vi har ikke mye
minne i kjølvannet.

196
00:09:33,636 --> 00:09:35,260
Og det er det de grå rutene er.

197
00:09:35,260 --> 00:09:40,540
Og det sannsynligvis føltes som det tok
mye lenger enn innsetting sortere, boble

198
00:09:40,540 --> 00:09:42,660
sortere, eller valg liksom.

199
00:09:42,660 --> 00:09:45,330
>> Men faktisk, fordi en
Mange av disse prosessene

200
00:09:45,330 --> 00:09:48,260
Det skjer på samme tid--
som er noe vi vil, igjen,

201
00:09:48,260 --> 00:09:51,100
snakke om når vi snakker om
rekursjon i en fremtidig video--

202
00:09:51,100 --> 00:09:53,799
denne algoritmen faktisk
klart er fundamentalt

203
00:09:53,799 --> 00:09:55,590
annerledes enn noe
vi har sett før

204
00:09:55,590 --> 00:09:58,820
men er også betydelig
mer effektiv.

205
00:09:58,820 --> 00:09:59,532
>> Hvorfor det?

206
00:09:59,532 --> 00:10:01,240
Vel, i verste
case scenario, har vi

207
00:10:01,240 --> 00:10:04,830
å splitte n elementer opp
og deretter rekombinere dem.

208
00:10:04,830 --> 00:10:06,680
Men når vi rekombinerer
dem, hva vi gjør

209
00:10:06,680 --> 00:10:11,110
er i utgangspunktet doble
størrelsen av de mindre matriser.

210
00:10:11,110 --> 00:10:14,260
Vi har en haug av ett element
arrays at vi effektivt

211
00:10:14,260 --> 00:10:16,290
kombinere i to element arrays.

212
00:10:16,290 --> 00:10:18,590
Og så tar vi dem
to element arrays

213
00:10:18,590 --> 00:10:21,890
og kombinere dem sammen til
fire element arrays, og så videre,

214
00:10:21,890 --> 00:10:26,130
og så videre, og så videre, helt til vi
ha en enkelt n elementsatsen.

215
00:10:26,130 --> 00:10:29,910
>> Men hvor mange doblinger
tar det å komme til n?

216
00:10:29,910 --> 00:10:31,460
Tenk tilbake til telefonboken eksempel.

217
00:10:31,460 --> 00:10:34,490
Hvor mange ganger må vi rive
telefonboken i to, hvor mange flere

218
00:10:34,490 --> 00:10:38,370
ganger må vi rive telefonboken
i to, hvis størrelsen på telefonboken

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

220
00:10:39,680 --> 00:10:41,960
Det er bare en, ikke sant?

221
00:10:41,960 --> 00:10:45,360
>> Så det er en slags
logaritmisk element her.

222
00:10:45,360 --> 00:10:48,590
Men vi har også fortsatt til minst
se på alle de n elementene.

223
00:10:48,590 --> 00:10:53,860
Så i verste fall
fusjonere slags kjører i n log n.

224
00:10:53,860 --> 00:10:56,160
Vi må se på
alle av de n elementene

225
00:10:56,160 --> 00:11:02,915
og vi må kombinere dem
sammen i log n sett med trinn.

226
00:11:02,915 --> 00:11:05,290
I beste fall
matrisen er perfekt sortert.

227
00:11:05,290 --> 00:11:06,300
Det er flott.

228
00:11:06,300 --> 00:11:09,980
Men basert på algoritmen vi har her,
vi har fortsatt å splitte og rekombinerer.

229
00:11:09,980 --> 00:11:13,290
Selv om det i dette tilfellet
rekombinerende er slags ineffektiv.

230
00:11:13,290 --> 00:11:14,720
Det er ikke nødvendig.

231
00:11:14,720 --> 00:11:17,580
Men vi fortsatt gå gjennom
hele prosessen uansett.

232
00:11:17,580 --> 00:11:21,290
>> Så i beste fall
og i verste fall

233
00:11:21,290 --> 00:11:24,970
denne algoritmen kjører i n log n gang.

234
00:11:24,970 --> 00:11:29,130
Merge sort er definitivt litt mer komplisert
enn de andre hovedsorteringsalgoritmer

235
00:11:29,130 --> 00:11:33,470
vi har snakket om CS50 men er
vesentlig kraftigere.

236
00:11:33,470 --> 00:11:35,400
>> Og så hvis du skulle finne
anledning til å trenge det

237
00:11:35,400 --> 00:11:38,480
eller å bruke den til å sortere en
store datasett, får

238
00:11:38,480 --> 00:11:41,940
hodet rundt ideen om rekursjon
kommer til å være veldig kraftig.

239
00:11:41,940 --> 00:11:45,270
Og det kommer til å gjøre
programmer egentlig mye mer effektiv

240
00:11:45,270 --> 00:11:48,700
bruker fusjonere slags versus noe annet.

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

242
00:11:49,640 --> 00:11:51,970
Dette er CS50.

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