1
00:00:00,000 --> 00:00:04,419
>> [MUSIK SPELA]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG Lloyd: OK, så en sammanslagning
sortera är ännu en algoritm

4
00:00:08,460 --> 00:00:11,200
att vi kan använda för att sortera ut
elementen i en array.

5
00:00:11,200 --> 00:00:14,480
Men när vi får se, det har fått en
mycket grundläggande skillnad

6
00:00:14,480 --> 00:00:17,850
från val Sortera, bubbla
sortera och insättningssortering

7
00:00:17,850 --> 00:00:20,280
som gör det egentligen ganska smart.

8
00:00:20,280 --> 00:00:24,290
>> Den grundläggande idén bakom merge
sort är att sortera mindre arrayer

9
00:00:24,290 --> 00:00:27,430
och sedan kombinera dessa matriser
tillsammans, eller slå samman them--

10
00:00:27,430 --> 00:00:31,440
hence name-- i sorterad ordning.

11
00:00:31,440 --> 00:00:34,230
Det sätt som merge sort gör
detta är genom att utnyttja ett verktyg

12
00:00:34,230 --> 00:00:37,290
kallas rekursion, vilket är vad
vi kommer att tala om snart,

13
00:00:37,290 --> 00:00:39,720
men vi har inte riktigt pratat om ännu.

14
00:00:39,720 --> 00:00:43,010
>> Här är den grundläggande idén bakom merge sort.

15
00:00:43,010 --> 00:00:46,320
Sortera den vänstra halvan av uppsättningen,
förutsatt n är större än 1.

16
00:00:46,320 --> 00:00:49,980
Och vad jag menar när jag säger
förutsatt n är större än 1 är,

17
00:00:49,980 --> 00:00:53,970
Jag tror att vi kan enas om att om en array
endast består av ett enda element,

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

19
00:00:54,680 --> 00:00:56,560
Vi egentligen inte behöver
att göra något för det.

20
00:00:56,560 --> 00:00:58,059
Vi kan bara förklara den ska sorteras.

21
00:00:58,059 --> 00:01:00,110
Det är bara ett enda element.

22
00:01:00,110 --> 00:01:03,610
>> Så pseudokod, återigen, är
sortera vänstra halvan av uppsättningen,

23
00:01:03,610 --> 00:01:08,590
sedan sortera högra halv arrayen,
sedan slå samman de två halvorna.

24
00:01:08,590 --> 00:01:11,040
Nu, redan du kan vara
tänker, det slags bara

25
00:01:11,040 --> 00:01:14,080
låter som du skjuter the--
du faktiskt inte göra någonting.

26
00:01:14,080 --> 00:01:16,330
Du säger sortera vänster
hälften, sortera den högra halvan,

27
00:01:16,330 --> 00:01:19,335
men du inte berättar
mig hur du gör det.

28
00:01:19,335 --> 00:01:22,220
>> Men kom ihåg att så länge
en array är ett enda element,

29
00:01:22,220 --> 00:01:23,705
vi kan förklara den sorteras.

30
00:01:23,705 --> 00:01:25,330
Då kan vi bara kombinera ihop dem.

31
00:01:25,330 --> 00:01:27,788
Och det är faktiskt
Grundtanken bakom merge sort,

32
00:01:27,788 --> 00:01:31,150
är att bryta ner det så att
dina arrayer är storlek en.

33
00:01:31,150 --> 00:01:33,430
Och sedan bygga därifrån.

34
00:01:33,430 --> 00:01:35,910
>> Merge sort är definitivt
en komplicerad algoritm.

35
00:01:35,910 --> 00:01:38,210
Och det är också lite
komplicerat att visualisera.

36
00:01:38,210 --> 00:01:41,870
Så förhoppningsvis, visualisering som jag
har här kommer att hjälpa dig att följa med.

37
00:01:41,870 --> 00:01:45,640
Och jag ska göra mitt bästa för att berätta saker
och gå igenom detta lite mer

38
00:01:45,640 --> 00:01:49,180
långsammare än de andra
bara för att förhoppningsvis få ditt huvud

39
00:01:49,180 --> 00:01:51,800
runt idéerna bakom merge sort.

40
00:01:51,800 --> 00:01:54,680
>> Så vi har samma array som
andra sorteringsalgoritm videor

41
00:01:54,680 --> 00:01:57,120
Om du har sett them--
en sex elementgrupp.

42
00:01:57,120 --> 00:02:02,110
Och vår pseudokoden här är typ
den vänstra halvan, sortera den högra halvan,

43
00:02:02,110 --> 00:02:03,890
slå samman de två halvorna.

44
00:02:03,890 --> 00:02:09,770
Så låt oss ta det mycket mörk tegelröd
array och sortera den vänstra halvan av det.

45
00:02:09,770 --> 00:02:13,380
>> Så för närvarande, vi kommer
att ignorera saker på höger sida.

46
00:02:13,380 --> 00:02:15,740
Det är där, men vi är
inte vid detta steg ännu.

47
00:02:15,740 --> 00:02:18,220
Vi är inte på sortera
högra halvan av matrisen.

48
00:02:18,220 --> 00:02:21,037
Vi är på sortera vänster
halv av arrayen.

49
00:02:21,037 --> 00:02:22,870
Och bara för sakens skull
att vara lite mer

50
00:02:22,870 --> 00:02:26,480
klar, så jag kan hänvisa
vad steg vi är på,

51
00:02:26,480 --> 00:02:29,800
Jag kommer att växla
Färgen på denna uppsättning till orange.

52
00:02:29,800 --> 00:02:33,190
Nu, vi pratar fortfarande om
Samma vänstra halvan av den ursprungliga arrayen.

53
00:02:33,190 --> 00:02:38,520
Men jag hoppas att genom att kunna
Se färgerna på olika poster,

54
00:02:38,520 --> 00:02:40,900
Det kommer att göra det lite mer
klart vad som händer här.

55
00:02:40,900 --> 00:02:43,270
>> OK, så nu har vi en
tre elementgrupp.

56
00:02:43,270 --> 00:02:46,420
Hur ska vi sortera vänstra halvan av detta
array, som fortfarande är det här steget?

57
00:02:46,420 --> 00:02:49,400
Vi försöker att sortera vänster
halv av tegelröd array--

58
00:02:49,400 --> 00:02:52,410
den vänstra halvan av vilka
Jag har nu färgad orange.

59
00:02:52,410 --> 00:02:54,840
>> Tja, vi kan prova och
upprepa denna process igen.

60
00:02:54,840 --> 00:02:56,756
Så vi är fortfarande i
mitten för att försöka sortera

61
00:02:56,756 --> 00:02:58,700
den vänstra halvan av full uppsättning.

62
00:02:58,700 --> 00:03:00,450
Den vänstra halvan av
array, jag ska bara

63
00:03:00,450 --> 00:03:03,910
godtyckligt besluta att den vänstra halvan
kommer att vara mindre än den högra halv,

64
00:03:03,910 --> 00:03:06,550
eftersom det händer
består av tre delar.

65
00:03:06,550 --> 00:03:11,260
>> Och så ska jag säga att
vänstra halv av den vänstra halv arrayen

66
00:03:11,260 --> 00:03:14,050
är bara elementet fem.

67
00:03:14,050 --> 00:03:18,360
Fem, är ett enda element
array, vi vet hur man sorterar det.

68
00:03:18,360 --> 00:03:21,615
Och så fem sorteras.

69
00:03:21,615 --> 00:03:22,990
Vi kommer bara att förklara det.

70
00:03:22,990 --> 00:03:24,890
Det är ett enda element array.

71
00:03:24,890 --> 00:03:29,015
>> Så vi har nu sorteras
vänstra halv av den vänstra half--

72
00:03:29,015 --> 00:03:33,190
eller snarare, har vi sorterat
vänstra halvan av orange.

73
00:03:33,190 --> 00:03:37,970
Så nu, för att ändå komplett
den totala uppsättningen vänstra halvan,

74
00:03:37,970 --> 00:03:43,481
vi måste sortera högra halvan
i orange, eller det här.

75
00:03:43,481 --> 00:03:44,230
Hur gör vi det?

76
00:03:44,230 --> 00:03:45,930
Tja, vi har en två elementgrupp.

77
00:03:45,930 --> 00:03:50,470
Så vi kan sortera vänstra halvan
av arrayen, vilket är två.

78
00:03:50,470 --> 00:03:52,090
Två är ett enda element.

79
00:03:52,090 --> 00:03:55,890
Så det är sorterade efter standard.
Då kan vi sortera högra halvan

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

81
00:03:58,530 --> 00:04:00,210
Det är typ av som standard.

82
00:04:00,210 --> 00:04:03,610
>> Detta är nu första gången
Vi har nått en sammanslagning steg.

83
00:04:03,610 --> 00:04:06,135
Vi har genomfört, men
Vi bevakar nu typ av kapslade down--

84
00:04:06,135 --> 00:04:08,420
och det är typ av knepigt
sak med rekursion är,

85
00:04:08,420 --> 00:04:10,930
du behöver för att hålla din
huvudet om var vi är.

86
00:04:10,930 --> 00:04:15,560
Så vi har sorts vänster
halv av den orange partiet.

87
00:04:15,560 --> 00:04:21,280
>> Och nu, vi är i mitten av sortering
den högra halvan av den orange delen.

88
00:04:21,280 --> 00:04:25,320
Och i den processen, vi är
nu på väg att bli på steget,

89
00:04:25,320 --> 00:04:27,850
slå samman de två halvorna.

90
00:04:27,850 --> 00:04:31,700
När vi tittar på de två halvorna
av arrayen, ser vi två och en.

91
00:04:31,700 --> 00:04:33,880
Vilket element är mindre?

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

93
00:04:35,160 --> 00:04:36,760
>> Sedan vilket element är mindre?

94
00:04:36,760 --> 00:04:38,300
Tja, det är två eller ingenting.

95
00:04:38,300 --> 00:04:39,910
Så det är två.

96
00:04:39,910 --> 00:04:43,690
Så nu, bara för att återigen rama
där vi är i sitt sammanhang,

97
00:04:43,690 --> 00:04:48,230
Vi har sorterat
vänstra halvan av den orange

98
00:04:48,230 --> 00:04:49,886
och den högra halvan av origo.

99
00:04:49,886 --> 00:04:52,510
Jag vet att jag har ändrat färgerna
igen, men det är där vi var.

100
00:04:52,510 --> 00:04:54,676
Och anledningen till att jag gjorde detta
beror på att denna process är

101
00:04:54,676 --> 00:04:57,870
kommer att fortsätta, iteration ned.

102
00:04:57,870 --> 00:05:00,500
Vi har sorterat vänster
hälften av den tidigare apelsin

103
00:05:00,500 --> 00:05:02,590
och den högra halvan av den tidigare apelsin.

104
00:05:02,590 --> 00:05:05,620
>> Nu måste vi slå ihop dem
två halvorna också.

105
00:05:05,620 --> 00:05:07,730
Det är det steg vi är på.

106
00:05:07,730 --> 00:05:11,440
Så vi anser alla
element som är nu grönt,

107
00:05:11,440 --> 00:05:12,972
den vänstra halvan av den ursprungliga arrayen.

108
00:05:12,972 --> 00:05:14,680
Och vi slå samman de
med användning av samma förfarande

109
00:05:14,680 --> 00:05:18,660
vi gjorde för att slå samman två
och en bara en stund sedan.

110
00:05:18,660 --> 00:05:23,080
>> Den vänstra halvan, den minsta
element på den vänstra halvan är fem.

111
00:05:23,080 --> 00:05:25,620
Det minsta elementet på
den högra halvan är en.

112
00:05:25,620 --> 00:05:27,370
Vilken av dem är mindre?

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

114
00:05:29,260 --> 00:05:32,250
>> Det minsta elementet på
den vänstra halvan är fem.

115
00:05:32,250 --> 00:05:35,540
Det minsta elementet på
den högra halvan är två.

116
00:05:35,540 --> 00:05:36,970
Vad är det minsta?

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

118
00:05:38,160 --> 00:05:41,540
Och sedan slutligen fem och
ingenting, kan vi säga fem.

119
00:05:41,540 --> 00:05:43,935
>> OK, så helheten, låt oss
ta en paus för en sekund

120
00:05:43,935 --> 00:05:46,080
och räkna ut var vi är.

121
00:05:46,080 --> 00:05:48,580
Om vi ​​startade från
början, vi

122
00:05:48,580 --> 00:05:51,640
har nu avslutats för
den totala matrisen bara

123
00:05:51,640 --> 00:05:53,810
ett steg i pseudokoden här.

124
00:05:53,810 --> 00:05:56,645
Vi har sorterat
vänstra halv av arrayen.

125
00:05:56,645 --> 00:05:59,490
>> Minns att det ursprungliga
För var fem, två, ett.

126
00:05:59,490 --> 00:06:02,570
Genom att gå igenom denna process
och häckar ner och upprepa,

127
00:06:02,570 --> 00:06:05,990
fortsätter att dela upp problemet
upp i mindre och mindre delar,

128
00:06:05,990 --> 00:06:09,670
Vi har nu avslutat
steg en av pseudokoden

129
00:06:09,670 --> 00:06:13,940
för hela start arrayen.

130
00:06:13,940 --> 00:06:16,670
Vi har sorterat sitt vänstra halvan.

131
00:06:16,670 --> 00:06:18,670
>> Så nu ska vi frysa där.

132
00:06:18,670 --> 00:06:23,087
Och nu ska vi sortera rätt
hälften av den ursprungliga matrisen.

133
00:06:23,087 --> 00:06:25,670
Och vi kommer att göra det genom att
gå igenom samma iterativa

134
00:06:25,670 --> 00:06:30,630
processen att bryta ner saker
och sedan slå samman dem tillsammans.

135
00:06:30,630 --> 00:06:34,290
>> Så den vänstra halvan av
rött, eller den vänstra halv

136
00:06:34,290 --> 00:06:38,830
av den högra hälften av den ursprungliga
array, jag kommer att säga är tre.

137
00:06:38,830 --> 00:06:40,312
Återigen, jag är konsekvent här.

138
00:06:40,312 --> 00:06:42,020
Om du har en udda
antal element, det

139
00:06:42,020 --> 00:06:44,478
spelar egentligen ingen roll om
du gör det vänstra mindre

140
00:06:44,478 --> 00:06:45,620
eller rätten en mindre.

141
00:06:45,620 --> 00:06:49,230
>> Det viktiga är att när du
stöta på detta problem i dirigering

142
00:06:49,230 --> 00:06:51,422
en sammanslagning, måste du vara konsekvent.

143
00:06:51,422 --> 00:06:53,505
Du behöver alltid antingen
göra en vänster sida mindre

144
00:06:53,505 --> 00:06:55,421
eller alltid behöver göra
den högra sidan mindre.

145
00:06:55,421 --> 00:06:57,720
Här har jag valt att alltid
göra vänster sida mindre

146
00:06:57,720 --> 00:07:04,380
när min samling, eller min
underuppställning är av ett udda storlek.

147
00:07:04,380 --> 00:07:07,420
>> Tre är ett enda element,
och så den sorteras.

148
00:07:07,420 --> 00:07:10,860
Vi har leveraged detta antagande
under hela vår process hittills.

149
00:07:10,860 --> 00:07:15,020
Så nu ska vi sortera rätt
halv av den högra halv,

150
00:07:15,020 --> 00:07:18,210
eller den högra halvan av den röda.

151
00:07:18,210 --> 00:07:20,390
>> Återigen måste vi dela ner det.

152
00:07:20,390 --> 00:07:21,910
Detta är inte en enda elementgrupp.

153
00:07:21,910 --> 00:07:23,970
Vi kan inte förklara den sortering.

154
00:07:23,970 --> 00:07:27,060
Och så först, vi kommer
att sortera den vänstra halvan.

155
00:07:27,060 --> 00:07:31,620
>> Den vänstra halvan är ett enda element,
så det är typ av som standard.

156
00:07:31,620 --> 00:07:34,840
Sedan ska vi sortera rätt
halv, vilket är ett enda element.

157
00:07:34,840 --> 00:07:41,250
Det är sorterade efter standard. Och nu,
vi kan slå ihop dessa två tillsammans.

158
00:07:41,250 --> 00:07:45,820
Fyra är mindre, och
då sex är mindre.

159
00:07:45,820 --> 00:07:48,870
>> Återigen, vad har vi gjort vid denna tidpunkt?

160
00:07:48,870 --> 00:07:52,512
Vi har sorterat vänster
hälften av den högra halvan.

161
00:07:52,512 --> 00:07:54,720
Eller gå tillbaka till den ursprungliga
färger som var där,

162
00:07:54,720 --> 00:07:57,875
Vi har sorterat vänster
halv av den mjukare rött.

163
00:07:57,875 --> 00:08:00,416
Det var ursprungligen en mörk tegel
rött och nu är det en mjukare rött,

164
00:08:00,416 --> 00:08:02,350
eller om det var en mjukare rött.

165
00:08:02,350 --> 00:08:05,145
>> Och sedan har vi sorteras
högra halvan av mjukare rött.

166
00:08:05,145 --> 00:08:08,270
Nu, ja, de är grön igen, precis
eftersom vi går igenom en process.

167
00:08:08,270 --> 00:08:10,720
Och vi måste upprepa
detta om och om igen.

168
00:08:10,720 --> 00:08:14,695
>> Så nu kan vi slå ihop dem
två halvor tillsammans.

169
00:08:14,695 --> 00:08:15,820
Och det är vad vi gör här.

170
00:08:15,820 --> 00:08:17,653
Så den svarta linjen bara
delas den vänstra halvan

171
00:08:17,653 --> 00:08:19,690
och den högra halvan av detta slag del.

172
00:08:19,690 --> 00:08:24,310
>> Vi jämför det minsta värdet
på vänstra sidan av array--

173
00:08:24,310 --> 00:08:26,710
eller ursäkta mig, den minsta
värdet på den vänstra halv

174
00:08:26,710 --> 00:08:30,790
till det minsta värdet av den högra
hälften och upptäcker att tre är mindre.

175
00:08:30,790 --> 00:08:32,530
Och nu lite av en optimering, eller hur?

176
00:08:32,530 --> 00:08:35,175
Det finns faktiskt inget
kvar på den vänstra sidan.

177
00:08:35,175 --> 00:08:37,440
>> Det finns inget kvar
på vänster sida,

178
00:08:37,440 --> 00:08:40,877
så vi kan på ett effektivt sätt
bara move-- vi kan deklarera

179
00:08:40,877 --> 00:08:42,960
resten av det är faktiskt
sorteras och bara lägga fram det

180
00:08:42,960 --> 00:08:45,126
på, eftersom det finns inget
annat att jämföra mot.

181
00:08:45,126 --> 00:08:49,140
Och vi vet att den högra sidan
av den högra sidan sorteras.

182
00:08:49,140 --> 00:08:52,770
>> OK, så nu ska vi frysa igen och
räkna ut var vi befinner oss i berättelsen.

183
00:08:52,770 --> 00:08:56,120
I den totala matrisen,
vad har vi åstadkommit?

184
00:08:56,120 --> 00:08:58,790
Vi har faktiskt åstadkomma
Nu steg ett och steg två.

185
00:08:58,790 --> 00:09:03,300
Vi sorterade den vänstra halvan, och
Vi sorterade den högra halvan.

186
00:09:03,300 --> 00:09:08,210
>> Så nu är allt som återstår för oss
att slå samman de två halvorna.

187
00:09:08,210 --> 00:09:11,670
Så vi jämför det lägsta värderade
elementet i varje halv av uppsättningen

188
00:09:11,670 --> 00:09:13,510
i sin tur och fortsätter.

189
00:09:13,510 --> 00:09:16,535
En är mindre än tre, så man går.

190
00:09:16,535 --> 00:09:19,770
>> Två är mindre än tre, så två går.

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

192
00:09:22,740 --> 00:09:25,820
Fyra är mindre än 5, så fyra går.

193
00:09:25,820 --> 00:09:30,210
Sedan fem är mindre än sex,
och sex är allt som återstår.

194
00:09:30,210 --> 00:09:31,820
>> Nu, jag vet, det var en hel del åtgärder.

195
00:09:31,820 --> 00:09:33,636
Och vi har lämnat en hel del
minne i vårt kölvatten.

196
00:09:33,636 --> 00:09:35,260
Och det är vad de grå rutorna är.

197
00:09:35,260 --> 00:09:40,540
Och det kändes nog som det tog en
mycket längre än insättningssortering, bubbla

198
00:09:40,540 --> 00:09:42,660
sort eller val slag.

199
00:09:42,660 --> 00:09:45,330
>> Men egentligen, eftersom en
Många av dessa processer

200
00:09:45,330 --> 00:09:48,260
händer på samma time--
vilket är något som vi ska, återigen,

201
00:09:48,260 --> 00:09:51,100
tala om när vi talar om
rekursion i ett framtida video--

202
00:09:51,100 --> 00:09:53,799
denna algoritm faktiskt
klart är i grunden

203
00:09:53,799 --> 00:09:55,590
annorlunda än något
vi har sett förut

204
00:09:55,590 --> 00:09:58,820
men är också betydligt
mer effektiv.

205
00:09:58,820 --> 00:09:59,532
>> Varför?

206
00:09:59,532 --> 00:10:01,240
Tja, i värsta
scenario, har vi

207
00:10:01,240 --> 00:10:04,830
att dela n element upp
och sedan kombinera dem.

208
00:10:04,830 --> 00:10:06,680
Men när vi återförenas
dem, vad vi gör

209
00:10:06,680 --> 00:10:11,110
är i princip en fördubbling av
storleken av de mindre matriser.

210
00:10:11,110 --> 00:10:14,260
Vi har ett gäng ett element
arrayer som vi effektivt

211
00:10:14,260 --> 00:10:16,290
kombinera till två elementuppsättningar.

212
00:10:16,290 --> 00:10:18,590
Och sedan tar vi dem
två elementuppsättningar

213
00:10:18,590 --> 00:10:21,890
och kombinera ihop dem till
fyra elementuppsättningar, och så vidare,

214
00:10:21,890 --> 00:10:26,130
och så vidare, och så vidare, tills vi
har en enda n elementgrupp.

215
00:10:26,130 --> 00:10:29,910
>> Men hur många fördubblingar
tar det att komma till n?

216
00:10:29,910 --> 00:10:31,460
Tänk tillbaka till telefonboken exempel.

217
00:10:31,460 --> 00:10:34,490
Hur många gånger ska vi behöva riva
telefonboken på mitten, hur många fler

218
00:10:34,490 --> 00:10:38,370
tider måste vi riva telefonboken
i halv, om storleken på telefonboken

219
00:10:38,370 --> 00:10:39,680
fördubblats?

220
00:10:39,680 --> 00:10:41,960
Det finns bara en, eller hur?

221
00:10:41,960 --> 00:10:45,360
>> Så det finns någon form av
logaritmisk inslag här.

222
00:10:45,360 --> 00:10:48,590
Men vi har fortfarande också att åtminstone
titta på alla av de n element.

223
00:10:48,590 --> 00:10:53,860
Så i värsta fall,
merge sort körs i n log n.

224
00:10:53,860 --> 00:10:56,160
Vi måste titta på
alla av de n elementen,

225
00:10:56,160 --> 00:11:02,915
och vi måste kombinera dem
tillsammans i log n uppsättningar av steg.

226
00:11:02,915 --> 00:11:05,290
I bästa fall,
matrisen är perfekt sorteras.

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

228
00:11:06,300 --> 00:11:09,980
Men baserat på den algoritm som vi har här,
vi har fortfarande att dela och kombinera.

229
00:11:09,980 --> 00:11:13,290
Även i detta fall, den
rekombination är typ av ineffektiv.

230
00:11:13,290 --> 00:11:14,720
Det behövs inte.

231
00:11:14,720 --> 00:11:17,580
Men vi fortfarande gå igenom
hela processen ändå.

232
00:11:17,580 --> 00:11:21,290
>> Så i bästa fall
och i värsta fall,

233
00:11:21,290 --> 00:11:24,970
denna algoritm körs i n log n tid.

234
00:11:24,970 --> 00:11:29,130
Merge sort är definitivt lite knepigare
än de andra stora sorteringsalgoritmer

235
00:11:29,130 --> 00:11:33,470
Vi har pratat om CS50 men är
betydligt mer kraftfull.

236
00:11:33,470 --> 00:11:35,400
>> Och så om du någonsin
tillfälle att behöva det

237
00:11:35,400 --> 00:11:38,480
eller att använda den för att sortera en
stor datamängd, få

238
00:11:38,480 --> 00:11:41,940
huvudet kring idén om rekursion
kommer att bli riktigt kraftfull.

239
00:11:41,940 --> 00:11:45,270
Och det kommer att göra din
program verkligen mycket effektivare

240
00:11:45,270 --> 00:11:48,700
använder merge sort kontra något annat.

241
00:11:48,700 --> 00:11:49,640
Jag är Doug Lloyd.

242
00:11:49,640 --> 00:11:51,970
Detta är CS50.

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