1
00:00:00,000 --> 00:00:04,419
>> [Muusika mängib]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, nii ühendamise
Sorteeri on järjekordne algoritm

4
00:00:08,460 --> 00:00:11,200
et saame kasutada praakima
elemendid massiivi.

5
00:00:11,200 --> 00:00:14,480
Aga nagu me näeme, see sai
väga põhimõtteline erinevus

6
00:00:14,480 --> 00:00:17,850
valikust omamoodi, mull
sorteerida ja sisestamise omamoodi

7
00:00:17,850 --> 00:00:20,280
et oleks tõesti kaval.

8
00:00:20,280 --> 00:00:24,290
>> Põhiidee ühendamine
Sorteeri on sorteerida väiksem massiivid

9
00:00:24,290 --> 00:00:27,430
ja siis ühendada need massiivid
koos, või ühendada them--

10
00:00:27,430 --> 00:00:31,440
seega name-- sorteeritud järjekorras.

11
00:00:31,440 --> 00:00:34,230
Nii, et liita omamoodi teeb
see on võimendades vahend

12
00:00:34,230 --> 00:00:37,290
nimetatakse rekursiooni, mis on see, mida
me ei kavatse rääkida kiiresti,

13
00:00:37,290 --> 00:00:39,720
kuid me ei ole tõesti rääkisime veel.

14
00:00:39,720 --> 00:00:43,010
>> Siin põhiidee ühendamine omamoodi.

15
00:00:43,010 --> 00:00:46,320
Sorteeri vasakul pool massiivi,
eeldades n on suurem kui 1.

16
00:00:46,320 --> 00:00:49,980
Ja mida ma mõtlen, kui ma ütlen
eeldades n on suurem kui 1 on,

17
00:00:49,980 --> 00:00:53,970
Ma arvan, et me saame kokku leppida, et kui massiivi
koosneb ainult ühe elemendi,

18
00:00:53,970 --> 00:00:54,680
see on järjestatud.

19
00:00:54,680 --> 00:00:56,560
Me tegelikult ei vaja
midagi teha sellega.

20
00:00:56,560 --> 00:00:58,059
Me lihtsalt kuulutada välja sorteerida.

21
00:00:58,059 --> 00:01:00,110
See on ainult üks element.

22
00:01:00,110 --> 00:01:03,610
>> Nii pseudokoodi on jällegi
Kuvatud vasakule poole massiiv,

23
00:01:03,610 --> 00:01:08,590
siis sorteerida õige pool massiivi,
siis ühendada kaks poolt kokku.

24
00:01:08,590 --> 00:01:11,040
Nüüd juba siis võiks olla
mõtlesin, et mingi lihtsalt

25
00:01:11,040 --> 00:01:14,080
kõlab nagu sa oled hakanud välja the--
sa tegelikult ei tee midagi.

26
00:01:14,080 --> 00:01:16,330
Ütled sorteeri vasakul
poole, sorteerida õige poole,

27
00:01:16,330 --> 00:01:19,335
aga sa ei räägi
mulle, kuidas sa teed seda.

28
00:01:19,335 --> 00:01:22,220
>> Kuid pidage meeles, et nii kaua, kui
massiivi on ühe elemendi,

29
00:01:22,220 --> 00:01:23,705
saame kuulutada järjestatud.

30
00:01:23,705 --> 00:01:25,330
Siis saame lihtsalt ühendada need kokku.

31
00:01:25,330 --> 00:01:27,788
Ja see on tegelikult
põhiline idee ühendada sorteerida,

32
00:01:27,788 --> 00:01:31,150
on jaotada see nii, et
Sinu massiivid on suurus üks.

33
00:01:31,150 --> 00:01:33,430
Ja siis te taastada sealt.

34
00:01:33,430 --> 00:01:35,910
>> Merge omamoodi on kindlasti
keeruline algoritm.

35
00:01:35,910 --> 00:01:38,210
Ja see on ka natuke
keeruline ette kujutada.

36
00:01:38,210 --> 00:01:41,870
Loodetavasti, visualiseerimine, et ma
on siin aitab teil jälgida mööda.

37
00:01:41,870 --> 00:01:45,640
Ja ma püüan oma parima, et jutustada asju
ja sõita läbi selle natuke rohkem

38
00:01:45,640 --> 00:01:49,180
aeglasemalt kui teised need
lihtsalt loodetavasti saan oma peaga

39
00:01:49,180 --> 00:01:51,800
ümber ideede ühendamine omamoodi.

40
00:01:51,800 --> 00:01:54,680
>> Nii et meil on sama rida nagu
teiste sorteerimisalgoritm videod

41
00:01:54,680 --> 00:01:57,120
Kui olete näinud them--
kuue element massiivi.

42
00:01:57,120 --> 00:02:02,110
Ja meie pseudokoodi koodi siin on omamoodi
Vasakul pool, sorteerida õige poole,

43
00:02:02,110 --> 00:02:03,890
ühendada kaks poolt kokku.

44
00:02:03,890 --> 00:02:09,770
Võtame seda väga tume telliskivi punaseks
massiivi ja sorteerida vasakule poole.

45
00:02:09,770 --> 00:02:13,380
>> Nii praegu, me ei kavatse
ignoreerida asju õige.

46
00:02:13,380 --> 00:02:15,740
See on olemas, kuid me oleme
mitte, et samm veel.

47
00:02:15,740 --> 00:02:18,220
Me ei ole hetkel Sorteeri
paremal pool massiivi.

48
00:02:18,220 --> 00:02:21,037
Oleme juures omamoodi vasakul
pool massiivi.

49
00:02:21,037 --> 00:02:22,870
Ja just huvides
olemise veidi rohkem

50
00:02:22,870 --> 00:02:26,480
selge, nii et ma ei viita
mida sammu me oleme,

51
00:02:26,480 --> 00:02:29,800
Ma lähen lülitada
värvi see komplekt oranžiks.

52
00:02:29,800 --> 00:02:33,190
Nüüd, me ikka räägime
Sama vasakule poole algse massiivi.

53
00:02:33,190 --> 00:02:38,520
Aga ma loodan, et nad saaksid
vaadake värve erinevaid objekte,

54
00:02:38,520 --> 00:02:40,900
see teen selle natuke rohkem
selge, mis toimub siin.

55
00:02:40,900 --> 00:02:43,270
>> OK, nii et nüüd on meil
kolm elementi massiivi.

56
00:02:43,270 --> 00:02:46,420
Kuidas sorteerida vasakule poole sellest
massiiv, mis on ikka see samm?

57
00:02:46,420 --> 00:02:49,400
Me püüame sorteerida vasakul
pool telliskivi punane array--

58
00:02:49,400 --> 00:02:52,410
Vasakul pool sellest
Olen nüüd oranž.

59
00:02:52,410 --> 00:02:54,840
>> Noh, me võiksime proovida ja
Seda protsessi korratakse uuesti.

60
00:02:54,840 --> 00:02:56,756
Nii et me oleme ikka
Keset üritab sorteerida

61
00:02:56,756 --> 00:02:58,700
Vasakul pool tervet rida.

62
00:02:58,700 --> 00:03:00,450
Vasakpoolne poole
massiiv, ma lähen lihtsalt

63
00:03:00,450 --> 00:03:03,910
suvaliselt otsustada, et vasakul pool
kasutatakse väiksemat paremal poolel,

64
00:03:03,910 --> 00:03:06,550
sest see juhtub
koosneb kolmest osast.

65
00:03:06,550 --> 00:03:11,260
>> Ja nii ma öelda, et
vasakul poolel vasakul poolel massiivi

66
00:03:11,260 --> 00:03:14,050
on lihtsalt element viis.

67
00:03:14,050 --> 00:03:18,360
Viis, olles üheks osaks
massiiv, me teame, kuidas sortida.

68
00:03:18,360 --> 00:03:21,615
Ja nii viis on järjestatud.

69
00:03:21,615 --> 00:03:22,990
Me elame kuulutada, et.

70
00:03:22,990 --> 00:03:24,890
See on ühe elemendi massiivist.

71
00:03:24,890 --> 00:03:29,015
>> Nii et me oleme nüüd sorteeritud
Vasakul pool vasakul half--

72
00:03:29,015 --> 00:03:33,190
või pigem oleme sorteeritud
Vasakul pool oranž.

73
00:03:33,190 --> 00:03:37,970
Nüüd, et ikka täielik
üldine massiiv vasakul pool,

74
00:03:37,970 --> 00:03:43,481
vajame sorteerida õige poole
oranž, või seda kraami.

75
00:03:43,481 --> 00:03:44,230
Kuidas me seda teeme?

76
00:03:44,230 --> 00:03:45,930
Noh, meil on kaks elementi massiivi.

77
00:03:45,930 --> 00:03:50,470
Nii saame sorteerida vasakule poole
massiivi, mis on kaks.

78
00:03:50,470 --> 00:03:52,090
Kaks on ühe elemendi.

79
00:03:52,090 --> 00:03:55,890
Nii see on järjestatud vaikimisi.
Siis on võimalik järjestada paremal pool

80
00:03:55,890 --> 00:03:58,530
Selle järjestuse osa, üks.

81
00:03:58,530 --> 00:04:00,210
See on omamoodi vaikimisi.

82
00:04:00,210 --> 00:04:03,610
>> See on nüüd esmakordselt
oleme jõudnud ühendamise samm.

83
00:04:03,610 --> 00:04:06,135
Oleme valmis, kuigi
me nüüd selline pesitseda down--

84
00:04:06,135 --> 00:04:08,420
ja see on omamoodi keeruline
asi rekurrentselt on,

85
00:04:08,420 --> 00:04:10,930
sa pead hoidma oma
pea kohta, kus me oleme.

86
00:04:10,930 --> 00:04:15,560
Nii me oleme omamoodi vasakul
poole apelsini osa.

87
00:04:15,560 --> 00:04:21,280
>> Ja nüüd, me oleme keset sorteerimine
paremal pool oranž osa.

88
00:04:21,280 --> 00:04:25,320
Ja selles protsessis oleme
nüüd hakkab olema samm,

89
00:04:25,320 --> 00:04:27,850
ühendada kaks poolt kokku.

90
00:04:27,850 --> 00:04:31,700
Kui me vaatame kaheks pooleks
massiivi, näeme kahe ja ühe.

91
00:04:31,700 --> 00:04:33,880
Milline element on väiksem?

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

93
00:04:35,160 --> 00:04:36,760
>> Siis mis element on väiksem?

94
00:04:36,760 --> 00:04:38,300
Noh, see on kaks või midagi.

95
00:04:38,300 --> 00:04:39,910
Seega on kaks.

96
00:04:39,910 --> 00:04:43,690
Nüüd, lihtsalt uuesti kadreerida
kus me oleme kontekstis

97
00:04:43,690 --> 00:04:48,230
oleme sorteeritud
Vasakul pool oranz

98
00:04:48,230 --> 00:04:49,886
ja paremal pool päritolu.

99
00:04:49,886 --> 00:04:52,510
Ma tean, et ma olen muutnud värvi
uuesti, kuid see, kus me olime.

100
00:04:52,510 --> 00:04:54,676
Ja põhjus, miks ma tegin seda
seetõttu, et see protsess on

101
00:04:54,676 --> 00:04:57,870
läheb edasi minema, iterating alla.

102
00:04:57,870 --> 00:05:00,500
Me oleme järjestatud vasakult
pool endise oranž

103
00:05:00,500 --> 00:05:02,590
ja paremal pool endise oranž.

104
00:05:02,590 --> 00:05:05,620
>> Nüüd on vaja ühendada need
kaheks pooleks kokku ka.

105
00:05:05,620 --> 00:05:07,730
See on samm me oleme.

106
00:05:07,730 --> 00:05:11,440
Nii arvame kõik
elemendid, mis on nüüd rohelised,

107
00:05:11,440 --> 00:05:12,972
vasakul poolel algse massiivi.

108
00:05:12,972 --> 00:05:14,680
Ja me ühinevad need
kasutades sama protsessi

109
00:05:14,680 --> 00:05:18,660
tegime ühinevad kaks
ja üks hetk tagasi.

110
00:05:18,660 --> 00:05:23,080
>> Vasakpoolne poole, väikseim
element vasakul pool on viis.

111
00:05:23,080 --> 00:05:25,620
Kõige väiksem element
paremal pool on üks.

112
00:05:25,620 --> 00:05:27,370
Kumb neist on väiksem?

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

114
00:05:29,260 --> 00:05:32,250
>> Kõige väiksem element
Vasakul pool on viis.

115
00:05:32,250 --> 00:05:35,540
Kõige väiksem element
paremal pool on kaks.

116
00:05:35,540 --> 00:05:36,970
Milline on väikseim?

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

118
00:05:38,160 --> 00:05:41,540
Ja siis lõpuks viis
midagi, me ei saa öelda viie.

119
00:05:41,540 --> 00:05:43,935
>> OK, nii suur pilt, olgem
pausi teist

120
00:05:43,935 --> 00:05:46,080
ja aru saada, kus me oleme.

121
00:05:46,080 --> 00:05:48,580
Kui me alustasime
Algusest peale oleme

122
00:05:48,580 --> 00:05:51,640
on nüüd lõpule
üldine massiiv lihtsalt

123
00:05:51,640 --> 00:05:53,810
üks samm pseudokoodi koodi siin.

124
00:05:53,810 --> 00:05:56,645
Meil on sorteeritud
Vasakul pool massiivi.

125
00:05:56,645 --> 00:05:59,490
>> Tuletame meelde, et esialgse
Selleks oli viis, kaks, üks.

126
00:05:59,490 --> 00:06:02,570
Minnes läbi selle protsessi
ja pesitsevate alla ja korrates,

127
00:06:02,570 --> 00:06:05,990
jätkates murda probleemi
väiksemateks ja väiksemateks osadeks,

128
00:06:05,990 --> 00:06:09,670
oleme nüüd valmis
samm üks pseudokoodi

129
00:06:09,670 --> 00:06:13,940
kogu lähtekohaks massiivi.

130
00:06:13,940 --> 00:06:16,670
Meil on järjestatud selle vasakul poolel.

131
00:06:16,670 --> 00:06:18,670
>> Nüüd oletame külmuda seal.

132
00:06:18,670 --> 00:06:23,087
Ja nüüd on omamoodi õigus
poole algse massiivi.

133
00:06:23,087 --> 00:06:25,670
Ja me ei kavatse teha, et
läbimas sama iteratiivne

134
00:06:25,670 --> 00:06:30,630
Protsessi purustamine asju ette
ja siis ühinevad nad kokku.

135
00:06:30,630 --> 00:06:34,290
>> Nii vasakul poolel
punane või vasakule poole

136
00:06:34,290 --> 00:06:38,830
õiguse poole originaal
massiiv, ma lähen ütlen on kolm.

137
00:06:38,830 --> 00:06:40,312
Jällegi, ma oleks järjepidevad.

138
00:06:40,312 --> 00:06:42,020
Kui teil on paaritu
elementide arv, seda

139
00:06:42,020 --> 00:06:44,478
ei ole tegelikult küsimus, kas
teete jäänud üks väiksem

140
00:06:44,478 --> 00:06:45,620
või õige väiksemad.

141
00:06:45,620 --> 00:06:49,230
>> Oluline on, et iga kord, kui
kogevad seda probleemi läbi

142
00:06:49,230 --> 00:06:51,422
ühendamise, pead olema järjekindel.

143
00:06:51,422 --> 00:06:53,505
Sa kas alati vaja
teeb vasakul äärel väiksem

144
00:06:53,505 --> 00:06:55,421
või alati vaja teha
paremal pool väiksem.

145
00:06:55,421 --> 00:06:57,720
Siin ma olen valinud alati
teha vasakpoolne väiksem

146
00:06:57,720 --> 00:07:04,380
kui minu rida, või minu
sub-massiivi, on paaritu suurus.

147
00:07:04,380 --> 00:07:07,420
>> Kolm on ühe elemendi,
ja nii see on järjestatud.

148
00:07:07,420 --> 00:07:10,860
Me oleme võimendatud, et eeldus
kogu meie kogu protsessi siiani.

149
00:07:10,860 --> 00:07:15,020
Vaatame nüüd sorteeri õigus
poolel õigus poole,

150
00:07:15,020 --> 00:07:18,210
või paremal pool punane.

151
00:07:18,210 --> 00:07:20,390
>> Jällegi, me peame jagama seda maha.

152
00:07:20,390 --> 00:07:21,910
See ei ole ühe elemendi massiivist.

153
00:07:21,910 --> 00:07:23,970
Me ei saa kuulutada järjestatud.

154
00:07:23,970 --> 00:07:27,060
Ja nii esimese, me ei kavatse
sorteeri vasakul pool.

155
00:07:27,060 --> 00:07:31,620
>> Vasakpoolne poolel on üksikosa,
nii et see on omamoodi vaikimisi.

156
00:07:31,620 --> 00:07:34,840
Siis me lähme sorteerida õige
poole, mis on üksikosa.

157
00:07:34,840 --> 00:07:41,250
See on järjestatud vaikimisi. Ja nüüd,
saame liita need kaks kokku.

158
00:07:41,250 --> 00:07:45,820
Neli on väiksem ja
siis kuus on väiksem.

159
00:07:45,820 --> 00:07:48,870
>> Jällegi, mida me oleme teinud sel hetkel?

160
00:07:48,870 --> 00:07:52,512
Me oleme järjestatud vasakult
poolel õigus poole.

161
00:07:52,512 --> 00:07:54,720
Või läheb tagasi algse
värvid, mis olid seal,

162
00:07:54,720 --> 00:07:57,875
oleme järjestatud vasakult
pool pehmem punaseks.

163
00:07:57,875 --> 00:08:00,416
Algselt oli tume tellis
punane ja nüüd on pehmem punane,

164
00:08:00,416 --> 00:08:02,350
või see oli pehmem punane.

165
00:08:02,350 --> 00:08:05,145
>> Ja siis oleme sorteeritud
paremal pool pehmem punane.

166
00:08:05,145 --> 00:08:08,270
Nüüd, samuti on nad jälle roheliseks, lihtsalt
sest me oleme läbimas protsessi.

167
00:08:08,270 --> 00:08:10,720
Ja me peame kordama
see ikka ja jälle.

168
00:08:10,720 --> 00:08:14,695
>> Nüüd saame liita need
kaheks pooleks kokku.

169
00:08:14,695 --> 00:08:15,820
Ja see, mida me siin teeme.

170
00:08:15,820 --> 00:08:17,653
Nii must joon ainult
jagatud vasakul pool

171
00:08:17,653 --> 00:08:19,690
ja paremal pool selline osa.

172
00:08:19,690 --> 00:08:24,310
>> Võrdleme väikseim väärtus
vasakul küljel array--

173
00:08:24,310 --> 00:08:26,710
või vabandage, väikseim
väärtus vasakul pool

174
00:08:26,710 --> 00:08:30,790
väikseima väärtuse õigus
poole ja leiavad, et kolm on väiksem.

175
00:08:30,790 --> 00:08:32,530
Ja nüüd natuke optimeerimine, eks?

176
00:08:32,530 --> 00:08:35,175
Seal on tegelikult midagi
vasakule vasakul küljel.

177
00:08:35,175 --> 00:08:37,440
>> Ei ole midagi jäänud
vasakul küljel,

178
00:08:37,440 --> 00:08:40,877
et saaksime tõhusalt
lihtsalt move-- saame kuulutada

179
00:08:40,877 --> 00:08:42,960
ülejäänud on tegelikult
sorteerida ja lihtsalt pühitakse see

180
00:08:42,960 --> 00:08:45,126
kohta, sest seal on midagi
muidu võrreldakse.

181
00:08:45,126 --> 00:08:49,140
Ja me teame, et paremal pool
paremale küljele on järjestatud.

182
00:08:49,140 --> 00:08:52,770
>> OK, nii et nüüd lähme uuesti külmutage ja
aru saada, kus me oleme lugu.

183
00:08:52,770 --> 00:08:56,120
Üldises massiiv,
mida oleme saavutanud?

184
00:08:56,120 --> 00:08:58,790
Me oleme tegelikult täita
Nüüd astub üks ja teine ​​etapp.

185
00:08:58,790 --> 00:09:03,300
Me järjestatud vasakult poole võrra ja
me järjestatud paremal pool.

186
00:09:03,300 --> 00:09:08,210
>> Nüüd on kõik, mis jääb üle
ühendada need kaks poolt kokku.

187
00:09:08,210 --> 00:09:11,670
Nii me võrdleme madalaim väärtus
element iga poole massiivi

188
00:09:11,670 --> 00:09:13,510
omakorda ja edasi.

189
00:09:13,510 --> 00:09:16,535
Üks on vähem kui kolm, nii et üks läheb.

190
00:09:16,535 --> 00:09:19,770
>> Kaks on vähem kui kolm, nii et kaks läheb.

191
00:09:19,770 --> 00:09:22,740
Kolm on alla 5, seega kolme läheb.

192
00:09:22,740 --> 00:09:25,820
Neli on alla 5, seega nelja läheb.

193
00:09:25,820 --> 00:09:30,210
Siis viis on vähem kui kuus,
ja kuus on kõik, mis jääb.

194
00:09:30,210 --> 00:09:31,820
>> Nüüd ma tean, et oli palju samme.

195
00:09:31,820 --> 00:09:33,636
Ja me oleme jätnud palju
mälu meie kiiluvees.

196
00:09:33,636 --> 00:09:35,260
Ja see, mida need hallid ruudud on.

197
00:09:35,260 --> 00:09:40,540
Ja see ilmselt tundus, et võttis
palju enam kui sisestamise sorteerida, mull

198
00:09:40,540 --> 00:09:42,660
Sorteeri või valikut omamoodi.

199
00:09:42,660 --> 00:09:45,330
>> Aga tegelikult, sest
palju neid protsesse

200
00:09:45,330 --> 00:09:48,260
toimuvad samal AEG_
mida me tulen jälle

201
00:09:48,260 --> 00:09:51,100
räägime, kui me räägime
recursion tulevases video--

202
00:09:51,100 --> 00:09:53,799
See algoritm tegelikult
selgelt on põhimõtteliselt

203
00:09:53,799 --> 00:09:55,590
teistsugune kui midagi
oleme näinud

204
00:09:55,590 --> 00:09:58,820
vaid on ka oluliselt
tõhusamaks.

205
00:09:58,820 --> 00:09:59,532
>> Miks nii?

206
00:09:59,532 --> 00:10:01,240
Noh, kõige hullem
stsenaariumi korral on meil

207
00:10:01,240 --> 00:10:04,830
jagada n elementi üles
ja siis rekombineerumise neid.

208
00:10:04,830 --> 00:10:06,680
Aga kui me rekombineerumise
need, mida me teeme

209
00:10:06,680 --> 00:10:11,110
on põhimõtteliselt kahekordistada
suurus väiksemate massiive.

210
00:10:11,110 --> 00:10:14,260
Meil on hunnik üks element
massiivid, et me tegelikult

211
00:10:14,260 --> 00:10:16,290
ühendada kahte elementi massiivi.

212
00:10:16,290 --> 00:10:18,590
Ja siis me võtame need
kaks elementi massiivi

213
00:10:18,590 --> 00:10:21,890
ja nende alusel koostada
nelja elemendi massiivid, ja nii edasi,

214
00:10:21,890 --> 00:10:26,130
ja nii edasi, ja nii edasi, kuni me
on üks n element massiivi.

215
00:10:26,130 --> 00:10:29,910
>> Aga kui palju kahekordistumine
see võtab, et saada n?

216
00:10:29,910 --> 00:10:31,460
Mõtle tagasi telefoniraamatust näiteks.

217
00:10:31,460 --> 00:10:34,490
Mitu korda me peame kiskuma
telefoniraamatust pooleks, kui palju

218
00:10:34,490 --> 00:10:38,370
korda on meil pisar telefoniraamat
poole, kui suurus telefoniraamatust

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

220
00:10:39,680 --> 00:10:41,960
Seal on lihtsalt üks, eks?

221
00:10:41,960 --> 00:10:45,360
>> Nii et mingisugune
logaritmiline element siin.

222
00:10:45,360 --> 00:10:48,590
Aga meil on ka veel vähemalt
vaata kõiki n elementi.

223
00:10:48,590 --> 00:10:53,860
Nii et halvimal juhul
liita omamoodi töötab n log n.

224
00:10:53,860 --> 00:10:56,160
Me peame vaatama
kõik n elemente,

225
00:10:56,160 --> 00:11:02,915
ja meil on neid omavahel kombineerida
koos log n toimingust.

226
00:11:02,915 --> 00:11:05,290
Parimal juhul stsenaarium,
massiiv on täiesti järjestatud.

227
00:11:05,290 --> 00:11:06,300
See on suurepärane.

228
00:11:06,300 --> 00:11:09,980
Aga põhineb algoritm meil siin,
meil on veel jagada ja rekombineerumise.

229
00:11:09,980 --> 00:11:13,290
Kuigi selles asjas
recombining on selline ebaefektiivne.

230
00:11:13,290 --> 00:11:14,720
Ei ole vaja.

231
00:11:14,720 --> 00:11:17,580
Aga meil on veel läbida
kogu protsessi niikuinii.

232
00:11:17,580 --> 00:11:21,290
>> Nii parimal juhul
ja halvimal juhul

233
00:11:21,290 --> 00:11:24,970
See algoritm töötab n log n korda.

234
00:11:24,970 --> 00:11:29,130
Merge omamoodi on kindlasti veidi keerukam
kui teised peamised sorteerimise algoritme

235
00:11:29,130 --> 00:11:33,470
oleme rääkinud CS50 kuid on
oluliselt võimsam.

236
00:11:33,470 --> 00:11:35,400
>> Ja kui sa kunagi leida
võimalus seda vajavad

237
00:11:35,400 --> 00:11:38,480
või kasutada seda sortida
suur andmekogum, saada

238
00:11:38,480 --> 00:11:41,940
oma pea ümber idee recursion
saab olema väga võimas.

239
00:11:41,940 --> 00:11:45,270
Ja see läheb teha oma
programmid tõesti palju tõhusam

240
00:11:45,270 --> 00:11:48,700
kasutades liita omamoodi versus midagi muud.

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

242
00:11:49,640 --> 00:11:51,970
See on CS50.

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