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

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG Lloyd: OK, joten yhdistäminen
lajitella on vielä toinen algoritmi

4
00:00:08,460 --> 00:00:11,200
että voimme käyttää selvittää
elementtejä jono.

5
00:00:11,200 --> 00:00:14,480
Mutta kuten näemme, se sai
hyvin perustavanlaatuinen ero

6
00:00:14,480 --> 00:00:17,850
valinnasta lajitella, kupla
lajitella, ja lisäyslajittelun

7
00:00:17,850 --> 00:00:20,280
jotka tekevät siitä oikeastaan ​​aika fiksu.

8
00:00:20,280 --> 00:00:24,290
>> Perusajatuksena yhdistämisen
lajitella on lajitella pienempi paneelit

9
00:00:24,290 --> 00:00:27,430
ja sitten yhdistää ne taulukot
yhdessä, tai yhdistää them--

10
00:00:27,430 --> 00:00:31,440
joten name-- sisään lajitellut järjestyksessä.

11
00:00:31,440 --> 00:00:34,230
Että sulautuvat eräänlainen tekee
tämä on hyödyntämällä työkalu

12
00:00:34,230 --> 00:00:37,290
nimeltään rekursio, joka on mitä
aiomme puhua pian,

13
00:00:37,290 --> 00:00:39,720
mutta emme ole oikeastaan ​​puhuneet vielä.

14
00:00:39,720 --> 00:00:43,010
>> Tässä perusajatus yhdistämisen lajitella.

15
00:00:43,010 --> 00:00:46,320
Järjestellä vasemmalla puolella array,
olettaen, että n on suurempi kuin 1.

16
00:00:46,320 --> 00:00:49,980
Ja mitä tarkoitan kun sanon
olettaen, että n on suurempi kuin 1 on,

17
00:00:49,980 --> 00:00:53,970
Mielestäni voimme olla samaa mieltä, että jos jono
vain koostuu yhdestä elementin,

18
00:00:53,970 --> 00:00:54,680
se on järjestetty.

19
00:00:54,680 --> 00:00:56,560
Emme oikeastaan ​​tarvitse
tehdä mitään sille.

20
00:00:56,560 --> 00:00:58,059
Voimme vain julistaa, että se voidaan lajitella.

21
00:00:58,059 --> 00:01:00,110
Se on vain yksi tekijä.

22
00:01:00,110 --> 00:01:03,610
>> Niin pseudokoodissa, jälleen, on
lajitella vasen puoli array,

23
00:01:03,610 --> 00:01:08,590
sitten lajitella oikea puoli jono,
sitten yhdistää puolikkaat yhteen.

24
00:01:08,590 --> 00:01:11,040
Nyt jo saatat olla
ajattelu, se tavallaan vain

25
00:01:11,040 --> 00:01:14,080
kuulostaa olet lykännyt the--
et oikeastaan ​​tee mitään.

26
00:01:14,080 --> 00:01:16,330
Sanot järjestellä vasen
puolet, lajitella oikea puoli,

27
00:01:16,330 --> 00:01:19,335
mutta mitä et kerro
minut teet sen.

28
00:01:19,335 --> 00:01:22,220
>> Mutta muista, että niin kauan kuin
array on yksi elementti,

29
00:01:22,220 --> 00:01:23,705
voimme julistaa, että se lajitellaan.

30
00:01:23,705 --> 00:01:25,330
Sitten voimme vain yhdistää ne yhteen.

31
00:01:25,330 --> 00:01:27,788
Ja se on todella
perusajatus yhdistämisen lajitella,

32
00:01:27,788 --> 00:01:31,150
on murtaa se alas niin, että
teidän paneelit ovat koko yksi.

33
00:01:31,150 --> 00:01:33,430
Ja sitten rakentaa sieltä.

34
00:01:33,430 --> 00:01:35,910
>> Merge sort on ehdottomasti
monimutkainen algoritmi.

35
00:01:35,910 --> 00:01:38,210
Ja se on myös hieman
monimutkainen visualisoida.

36
00:01:38,210 --> 00:01:41,870
Joten toivottavasti, visualisointi, että olen
on täällä auttaa sinua seurata pitkin.

37
00:01:41,870 --> 00:01:45,640
Ja minä yritän parhaani mukaan kertoa asioita
ja eteenpäin tätä hieman enemmän

38
00:01:45,640 --> 00:01:49,180
hitaasti kuin toisilla
vain toivottavasti saa pään

39
00:01:49,180 --> 00:01:51,800
ympäri ideoista yhdistämisen lajitella.

40
00:01:51,800 --> 00:01:54,680
>> Joten meillä on sama joukko kuin
muut lajittelualgoritmi videoita

41
00:01:54,680 --> 00:01:57,120
jos olet nähnyt them--
kuusi alkiotaulukon.

42
00:01:57,120 --> 00:02:02,110
Ja meidän pseudokoodilla koodi tässä eräänlainen
vasen puoli, lajitella oikea puoli,

43
00:02:02,110 --> 00:02:03,890
yhdistää puolikkaat yhteen.

44
00:02:03,890 --> 00:02:09,770
Joten ottaa tämän hyvin tumma tiilenpunainen
array ja lajitella vasemmalle puolet.

45
00:02:09,770 --> 00:02:13,380
>> Joten toistaiseksi aiomme
sivuuttaa kamaa oikealla.

46
00:02:13,380 --> 00:02:15,740
Se on olemassa, mutta olemme
ei siinä vaiheessa vielä.

47
00:02:15,740 --> 00:02:18,220
Emme ole lajitella
oikealla puolella jono.

48
00:02:18,220 --> 00:02:21,037
Me olemme tavallaan vasemmalla
puolet jono.

49
00:02:21,037 --> 00:02:22,870
Ja vain vuoksi
olemisen hieman

50
00:02:22,870 --> 00:02:26,480
kirkas, joten en voi viitata
mitä askel me olemme,

51
00:02:26,480 --> 00:02:29,800
Aion vaihtaa
väri Tästä oranssiksi.

52
00:02:29,800 --> 00:02:33,190
Nyt olemme yhä puhumme
sama vasen puolet alkuperäisestä array.

53
00:02:33,190 --> 00:02:38,520
Mutta toivon, että voidessaan
viittaavat värit eri kohteita,

54
00:02:38,520 --> 00:02:40,900
se tulee tehdä hieman enemmän
selvää, mitä täällä tapahtuu.

55
00:02:40,900 --> 00:02:43,270
>> OK, joten nyt meillä on
kolme alkiotaulukko.

56
00:02:43,270 --> 00:02:46,420
Miten lajitella vasen puoli tämän
array, joka on vielä tässä vaiheessa?

57
00:02:46,420 --> 00:02:49,400
Yritämme lajitella vasemmalle
puolet tiilenpunainen array--

58
00:02:49,400 --> 00:02:52,410
vasen puoli, jonka
Olen nyt oranssinvärinen.

59
00:02:52,410 --> 00:02:54,840
>> No, voisimme yrittää
Toistan tämän prosessin uudelleen.

60
00:02:54,840 --> 00:02:56,756
Joten olemme edelleen
keskellä yrittää lajitella

61
00:02:56,756 --> 00:02:58,700
vasemmalla puolella täyden valikoiman.

62
00:02:58,700 --> 00:03:00,450
Vasemmalla puolella
array, olen juuri menossa

63
00:03:00,450 --> 00:03:03,910
mielivaltaisesti päättää, että vasen puoli
on pienempi kuin oikea puoli,

64
00:03:03,910 --> 00:03:06,550
koska tämä tapahtuu
koostuvat kolmesta osasta.

65
00:03:06,550 --> 00:03:11,260
>> Ja niin aion sanoa, että
vasen puoli vasen puoli array

66
00:03:11,260 --> 00:03:14,050
on vain osa viisi.

67
00:03:14,050 --> 00:03:18,360
Viisi, että yksi elementti
array, tiedämme, miten lajitella.

68
00:03:18,360 --> 00:03:21,615
Ja niin viisi lajitellaan.

69
00:03:21,615 --> 00:03:22,990
Olemme juuri menossa toteamaan.

70
00:03:22,990 --> 00:03:24,890
Se on yksi alkiotaulukon.

71
00:03:24,890 --> 00:03:29,015
>> Joten olemme nyt lajiteltu
vasen puoli vasemman half--

72
00:03:29,015 --> 00:03:33,190
tai pikemminkin olemme lajiteltu
vasen puoli oranssi.

73
00:03:33,190 --> 00:03:37,970
Joten nyt, jotta vielä valmis
yleinen array vasen puoli,

74
00:03:37,970 --> 00:03:43,481
meidän täytyy lajitella oikea puoli
oranssi, tai tätä kamaa.

75
00:03:43,481 --> 00:03:44,230
Miten me sen teemme?

76
00:03:44,230 --> 00:03:45,930
No, meillä on kaksi alkiotaulukon.

77
00:03:45,930 --> 00:03:50,470
Joten voimme lajitella vasen puoli
array, joka on kaksi.

78
00:03:50,470 --> 00:03:52,090
Kaksi on yksi elementti.

79
00:03:52,090 --> 00:03:55,890
Joten se on lajiteltu oletuksena.
Sitten voimme lajitella oikea puoli

80
00:03:55,890 --> 00:03:58,530
sen osan array, yksi.

81
00:03:58,530 --> 00:04:00,210
Se on tavallaan oletuksena.

82
00:04:00,210 --> 00:04:03,610
>> Tämä on nyt ensimmäistä kertaa
olemme saavuttaneet yhdistämisen askel.

83
00:04:03,610 --> 00:04:06,135
Olemme saattaneet, vaikka
olemme nyt sellainen sisäkkäisiä down--

84
00:04:06,135 --> 00:04:08,420
ja se on tavallaan hankala
juttu rekursio on,

85
00:04:08,420 --> 00:04:10,930
sinun täytyy pitää
suunnata noin missä olemme.

86
00:04:10,930 --> 00:04:15,560
Joten olemme tavallaan vasemman
puolet oranssi osan.

87
00:04:15,560 --> 00:04:21,280
>> Ja nyt, olemme keskellä lajittelu
oikea puoli oranssi osan.

88
00:04:21,280 --> 00:04:25,320
Ja tässä prosessissa, olemme
nyt noin olla askel,

89
00:04:25,320 --> 00:04:27,850
yhdistää puolikkaat yhteen.

90
00:04:27,850 --> 00:04:31,700
Kun katsomme puolikkaat
array, näemme kaksi ja yksi.

91
00:04:31,700 --> 00:04:33,880
Joka elementti on pienempi?

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

93
00:04:35,160 --> 00:04:36,760
>> Sitten joka elementti on pienempi?

94
00:04:36,760 --> 00:04:38,300
No, se on kaksi tai ei mitään.

95
00:04:38,300 --> 00:04:39,910
Joten se on kaksi.

96
00:04:39,910 --> 00:04:43,690
Joten nyt, vain jälleen kehystää
missä olemme yhteydessä,

97
00:04:43,690 --> 00:04:48,230
olemme lajiteltu
vasemmalla puolella oranssi

98
00:04:48,230 --> 00:04:49,886
ja oikea puoli alkuperää.

99
00:04:49,886 --> 00:04:52,510
Tiedän Olen muuttanut värit
jälleen, mutta siitähän olimme.

100
00:04:52,510 --> 00:04:54,676
Ja syy Tein
on, koska tämä prosessi on

101
00:04:54,676 --> 00:04:57,870
menossa pitämään menossa, iteroimalla alas.

102
00:04:57,870 --> 00:05:00,500
Olemme järjestetty vasen
puolet entisen oranssi

103
00:05:00,500 --> 00:05:02,590
ja oikea puoli entisen oranssi.

104
00:05:02,590 --> 00:05:05,620
>> Nyt meidän täytyy yhdistää nämä
puolikkaat yhdessä liikaa.

105
00:05:05,620 --> 00:05:07,730
Se on askel me olemme.

106
00:05:07,730 --> 00:05:11,440
Joten pidämme kaikki
elementtejä, jotka ovat nyt vihreä,

107
00:05:11,440 --> 00:05:12,972
vasen puolet alkuperäisestä array.

108
00:05:12,972 --> 00:05:14,680
Ja me yhdistää ne
käyttäen samaa prosessia

109
00:05:14,680 --> 00:05:18,660
teimme yhdistämällä kaksi
ja yksi vain hetki sitten.

110
00:05:18,660 --> 00:05:23,080
>> Vasen puoli, pienin
elementti vasemmalla puolella on viisi.

111
00:05:23,080 --> 00:05:25,620
Pienin elementti
oikea puoli on yksi.

112
00:05:25,620 --> 00:05:27,370
Mikä näistä on pienempi?

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

114
00:05:29,260 --> 00:05:32,250
>> Pienin elementti
vasen puoli on viisi.

115
00:05:32,250 --> 00:05:35,540
Pienin elementti
oikea puoli on kaksi.

116
00:05:35,540 --> 00:05:36,970
Mikä on pienin?

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

118
00:05:38,160 --> 00:05:41,540
Ja sitten lopuksi viisi ja
mitään, voimme sanoa viisi.

119
00:05:41,540 --> 00:05:43,935
>> OK, joten iso kuva, katsotaanpa
taukoa toisen

120
00:05:43,935 --> 00:05:46,080
ja selvittää, missä olemme.

121
00:05:46,080 --> 00:05:48,580
Jos me alkoi
alusta, me

122
00:05:48,580 --> 00:05:51,640
on nyt valmistunut
yleinen array vain

123
00:05:51,640 --> 00:05:53,810
yksi askel pseudokoodin koodi tähän.

124
00:05:53,810 --> 00:05:56,645
Olemme lajiteltu
vasemmalla puolella jono.

125
00:05:56,645 --> 00:05:59,490
>> Muista, että alkuperäinen
järjestys oli viisi, kaksi, yksi.

126
00:05:59,490 --> 00:06:02,570
Käymällä läpi tämän prosessin
ja pesivät alas ja toistetaan,

127
00:06:02,570 --> 00:06:05,990
edelleen rikkoa ongelma
pienempiin ja pienempiin osiin,

128
00:06:05,990 --> 00:06:09,670
olemme nyt valmistunut
vaihe yksi pseudokoodina

129
00:06:09,670 --> 00:06:13,940
koko alkaa jono.

130
00:06:13,940 --> 00:06:16,670
Olemme lajiteltu sen vasen puoli.

131
00:06:16,670 --> 00:06:18,670
>> Joten Nyt jäädyttää siellä.

132
00:06:18,670 --> 00:06:23,087
Ja Nyt lajitella oikealla
puolet alkuperäisestä array.

133
00:06:23,087 --> 00:06:25,670
Ja aiomme tehdä, että
läpi samaa iteratiivista

134
00:06:25,670 --> 00:06:30,630
prosessi rikkoa asioita alas
ja sitten yhdistämällä ne yhteen.

135
00:06:30,630 --> 00:06:34,290
>> Joten vasemmalla puolella
punainen, tai vasen puoli

136
00:06:34,290 --> 00:06:38,830
oikeuden puolet alkuperäisestä
array, aion sanoa on kolme.

137
00:06:38,830 --> 00:06:40,312
Jälleen olen johdonmukainen täällä.

138
00:06:40,312 --> 00:06:42,020
Jos sinulla on pariton
useita tekijöitä, se

139
00:06:42,020 --> 00:06:44,478
ei ole oikeastaan ​​väliä, onko
teet vasemmalle yksi pienempi

140
00:06:44,478 --> 00:06:45,620
tai oikea pienempi.

141
00:06:45,620 --> 00:06:49,230
>> Tärkeintä on, että aina kun
tämä ongelma ilmenee suorittamisessa

142
00:06:49,230 --> 00:06:51,422
yhdistämisen, sinun täytyy olla johdonmukainen.

143
00:06:51,422 --> 00:06:53,505
Joko aina tarvitse
tehdä vasemmalla puolella pienempi

144
00:06:53,505 --> 00:06:55,421
tai aina tarvitse tehdä
oikealla puolella pienempi.

145
00:06:55,421 --> 00:06:57,720
Täällä, olen päättänyt aina
tehdä vasemmalla puolella pienempi

146
00:06:57,720 --> 00:07:04,380
kun minun array, tai minun
aliryhmälle, on pariton koon.

147
00:07:04,380 --> 00:07:07,420
>> Kolme on yksi elementti,
ja niin se lajitellaan.

148
00:07:07,420 --> 00:07:10,860
Olemme velkarahalla että oletus
koko meidän koko prosessin toistaiseksi.

149
00:07:10,860 --> 00:07:15,020
Joten Nyt lajitella oikealla
puolet oikea puoli,

150
00:07:15,020 --> 00:07:18,210
tai oikealla puolella punainen.

151
00:07:18,210 --> 00:07:20,390
>> Jälleen meidän täytyy jakaa tämän alas.

152
00:07:20,390 --> 00:07:21,910
Tämä ei ole yksittäinen tekijä array.

153
00:07:21,910 --> 00:07:23,970
Emme voi julistaa sen lajiteltu.

154
00:07:23,970 --> 00:07:27,060
Ja niin ensimmäinen aiomme
lajitella vasen puoli.

155
00:07:27,060 --> 00:07:31,620
>> Vasen puoli on yksittäinen tekijä,
joten se on tavallaan oletuksena.

156
00:07:31,620 --> 00:07:34,840
Sitten aiomme lajitella oikealle
puoli, joka on yksi elementti.

157
00:07:34,840 --> 00:07:41,250
Se lajiteltu oletuksena. Ja nyt,
voimme yhdistää nämä kaksi yhdessä.

158
00:07:41,250 --> 00:07:45,820
Neljä on pienempi, ja
sitten kuusi on pienempi.

159
00:07:45,820 --> 00:07:48,870
>> Jälleen mitä olemme tehneet tässä vaiheessa?

160
00:07:48,870 --> 00:07:52,512
Olemme järjestetty vasen
puolet oikea puoli.

161
00:07:52,512 --> 00:07:54,720
Tai menee takaisin alkuperäiseen
värit, jotka olivat siellä,

162
00:07:54,720 --> 00:07:57,875
olemme lajiteltu vasen
puolet pehmeämpi punainen.

163
00:07:57,875 --> 00:08:00,416
Se oli alun perin tumma tiili
punainen ja nyt se on pehmeämpi punainen,

164
00:08:00,416 --> 00:08:02,350
tai se oli pehmeämpi punainen.

165
00:08:02,350 --> 00:08:05,145
>> Ja sitten olemme lajiteltu
oikea puoli pehmeämpi punainen.

166
00:08:05,145 --> 00:08:08,270
Nyt, hyvin, he ovat vihreä jälleen, vain
koska olemme menossa läpi prosessin.

167
00:08:08,270 --> 00:08:10,720
Ja meidän on toistettava
tämä uudestaan ​​ja uudestaan.

168
00:08:10,720 --> 00:08:14,695
>> Joten nyt voimme yhdistää nämä
puolikkaat yhteen.

169
00:08:14,695 --> 00:08:15,820
Ja sitähän me teemme täällä.

170
00:08:15,820 --> 00:08:17,653
Niin musta viiva vain
jaettu vasen puoli

171
00:08:17,653 --> 00:08:19,690
ja oikea puoli tämmöinen osan.

172
00:08:19,690 --> 00:08:24,310
>> Vertaamme pienin arvo
vasemmalla puolella array--

173
00:08:24,310 --> 00:08:26,710
tai anteeksi, pienin
arvo vasen puoli

174
00:08:26,710 --> 00:08:30,790
pienintä arvoa oikea
puoli ja huomaat, että kolme on pienempi.

175
00:08:30,790 --> 00:08:32,530
Ja nyt vähän optimoinnin, eikö?

176
00:08:32,530 --> 00:08:35,175
Ei oikeastaan ​​mitään
vasemmalle vasemmalla puolella.

177
00:08:35,175 --> 00:08:37,440
>> Ei ole mitään jäljellä
vasemmalla puolella,

178
00:08:37,440 --> 00:08:40,877
joten voimme tehokkaasti
vain move-- voimme julistaa

179
00:08:40,877 --> 00:08:42,960
loput se on todella
lajiteltu ja vain tack se

180
00:08:42,960 --> 00:08:45,126
on, koska ei ole mitään
muu vertailla vastaan.

181
00:08:45,126 --> 00:08:49,140
Ja me tiedämme, että oikea puoli
oikean puolen lajitellaan.

182
00:08:49,140 --> 00:08:52,770
>> OK, joten nyt katsotaanpa jäädyttää uudelleen ja
selvittää missä olemme tarina.

183
00:08:52,770 --> 00:08:56,120
Kun yleinen array,
mitä olemme aikaan?

184
00:08:56,120 --> 00:08:58,790
Olemme todella saavuttaa
nyt vaiheet yksi ja toinen vaihe.

185
00:08:58,790 --> 00:09:03,300
Olemme järjestetty vasen puoli, ja
me lajitellaan oikea puoli.

186
00:09:03,300 --> 00:09:08,210
>> Joten nyt, jäljellä on meille
yhdistää nämä kaksi puolikasta yhteen.

187
00:09:08,210 --> 00:09:11,670
Joten vertaamme alin arvostettu
elementti kummankin puoliskon array

188
00:09:11,670 --> 00:09:13,510
puolestaan ​​ja edetä.

189
00:09:13,510 --> 00:09:16,535
Yksi on vähemmän kuin kolme, niin mennään.

190
00:09:16,535 --> 00:09:19,770
>> Kaksi on vähemmän kuin kolme, joten kaksi menee.

191
00:09:19,770 --> 00:09:22,740
Kolme on alle 5, niin kolme menee.

192
00:09:22,740 --> 00:09:25,820
Neljä on alle 5, niin neljä menee.

193
00:09:25,820 --> 00:09:30,210
Sitten viisi on alle kuusi,
ja kuusi on kaikki pysyy.

194
00:09:30,210 --> 00:09:31,820
>> Nyt tiedän, että oli runsaasti portaita.

195
00:09:31,820 --> 00:09:33,636
Ja olemme jätti paljon
muistin meidän vanavedessä.

196
00:09:33,636 --> 00:09:35,260
Ja sitähän harmaita neliöt ovat.

197
00:09:35,260 --> 00:09:40,540
Ja se luultavasti tuntui että otti
paljon kauemmin kuin lisäyslajittelun, kupla

198
00:09:40,540 --> 00:09:42,660
lajitella, tai valinta lajitella.

199
00:09:42,660 --> 00:09:45,330
>> Mutta todellisuudessa, koska
Monet näistä prosesseista

200
00:09:45,330 --> 00:09:48,260
tapahtuu samaan time--
joka on jotain käymme, jälleen,

201
00:09:48,260 --> 00:09:51,100
puhua, kun puhumme
rekursio tulevassa video--

202
00:09:51,100 --> 00:09:53,799
tämä algoritmi todella
selvästi on pohjimmiltaan

203
00:09:53,799 --> 00:09:55,590
eri kuin mitään
olemme nähneet aiemmin

204
00:09:55,590 --> 00:09:58,820
mutta on myös huomattavasti
tehokkaampi.

205
00:09:58,820 --> 00:09:59,532
>> Miksi näin?

206
00:09:59,532 --> 00:10:01,240
No, pahimmassa
tapauksessa, meillä on

207
00:10:01,240 --> 00:10:04,830
jakaa n elementtiä ylös
ja sitten recombine niitä.

208
00:10:04,830 --> 00:10:06,680
Mutta kun me recombine
heille, mitä teemme

209
00:10:06,680 --> 00:10:11,110
on periaatteessa kaksinkertaistaa
koko pienempi paneelit.

210
00:10:11,110 --> 00:10:14,260
Meillä on joukko yhden elementin
paneelit että me tehokkaasti

211
00:10:14,260 --> 00:10:16,290
yhdistää kahteen elementtiin taulukot.

212
00:10:16,290 --> 00:10:18,590
Ja sitten otamme ne
kaksi elementin taulukot

213
00:10:18,590 --> 00:10:21,890
ja yhdistellä niitä
neljä elementti paneelit, ja niin edelleen,

214
00:10:21,890 --> 00:10:26,130
ja niin edelleen, ja niin edelleen, kunnes
on yksi n alkiotaulukon.

215
00:10:26,130 --> 00:10:29,910
>> Mutta kuinka moni kahdentumisen
kestää päästä n?

216
00:10:29,910 --> 00:10:31,460
Muistelen puhelinluetteloon esimerkki.

217
00:10:31,460 --> 00:10:34,490
Kuinka monta kertaa meidän täytyy repiä
puhelinluettelon kahtia, kuinka paljon enemmän

218
00:10:34,490 --> 00:10:38,370
kertaa meillä on repiä puhelinluettelo
kahtia, jos koko puhelinluettelon

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

220
00:10:39,680 --> 00:10:41,960
On vain yksi, oikea?

221
00:10:41,960 --> 00:10:45,360
>> Joten ei jonkinlainen
logaritminen elementti täällä.

222
00:10:45,360 --> 00:10:48,590
Mutta meillä on myös vielä ainakin
tarkastella kaikkia n alkiota.

223
00:10:48,590 --> 00:10:53,860
Joten pahimmassa tapauksessa,
yhdistää lajitella toimii n log n.

224
00:10:53,860 --> 00:10:56,160
Meidän on tarkasteltava
kaikki n elementtejä,

225
00:10:56,160 --> 00:11:02,915
ja meidän on yhdistää ne
yhdessä log n sarjaa vaiheita.

226
00:11:02,915 --> 00:11:05,290
Parhaassa tapauksessa,
array on täydellisesti lajitellaan.

227
00:11:05,290 --> 00:11:06,300
Sepä hienoa.

228
00:11:06,300 --> 00:11:09,980
Vaan perustuu algoritmiin olemme täällä,
meillä on vielä jakaa ja yhdistää.

229
00:11:09,980 --> 00:11:13,290
Vaikka tässä tapauksessa,
yhdistimeen on tavallaan tehoton.

230
00:11:13,290 --> 00:11:14,720
Sitä ei tarvita.

231
00:11:14,720 --> 00:11:17,580
Mutta me silti mennä läpi
koko prosessin muutenkin.

232
00:11:17,580 --> 00:11:21,290
>> Joten parhaassa tapauksessa
ja pahimmassa tapauksessa,

233
00:11:21,290 --> 00:11:24,970
tämä algoritmi toimii n log n aikaa.

234
00:11:24,970 --> 00:11:29,130
Merge sort on ehdottomasti hieman hankalampaa
kuin muut tärkeimmät lajittelualgoritmeja

235
00:11:29,130 --> 00:11:33,470
olemme puhuneet CS50 mutta on
huomattavasti tehokkaampi.

236
00:11:33,470 --> 00:11:35,400
>> Ja joten jos koskaan löytää
tilaisuus tarvitse sitä

237
00:11:35,400 --> 00:11:38,480
tai käyttää sitä lajitella
suuri tietokokonaisuutta, saada

238
00:11:38,480 --> 00:11:41,940
pään ympärillä ajatus rekursio
tulee olemaan todella voimakas.

239
00:11:41,940 --> 00:11:45,270
Ja se tulee tehdä
ohjelmat todella paljon tehokkaampaa

240
00:11:45,270 --> 00:11:48,700
käyttäen yhdistää lajitella vastaan ​​mitään muuta.

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

242
00:11:49,640 --> 00:11:51,970
Tämä on CS50.

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