1
00:00:00,000 --> 00:00:03,227
[SKAN MŪZIKA]

2
00:00:03,227 --> 00:00:03,896
DAGS LOIDS: Labi, līdz šim esam
runājuši par dažiem kārtošanas 

3
00:00:03,896 --> 00:00:04,565
algoritmiem, ar kuriem, cerams, ir
diezgan vienkārši strādāt. 

4
00:00:11,570 --> 00:00:12,934
Mums ir burbuļa kārtošana,
ievietošanas kārtošana un atlases 

5
00:00:12,934 --> 00:00:14,299
kārtošana. 

6
00:00:14,299 --> 00:00:17,929
Un mēs zinām, ka tām ir sava veida
sliktākā scenārija izpildlaiks n 

7
00:00:17,929 --> 00:00:21,560
kvadrātā. 

8
00:00:21,560 --> 00:00:23,430
Vai mēs varam to uzlabot?

9
00:00:23,430 --> 00:00:26,005
Nu, atbilde ir jā, mēs varam,
izmantojot algoritmu, ko sauc par 

10
00:00:26,005 --> 00:00:28,580
sapludināšanas kārtošanu. 

11
00:00:28,580 --> 00:00:32,043
Sapludināšanas kārtošanas ideja ir
– sakārtot mazākus masīvus un pēc 

12
00:00:32,043 --> 00:00:35,506
tam apvienot šos masīvus vai
apvienot tos sakārtotā secībā, kā 

13
00:00:35,506 --> 00:00:38,970
norādīts paša algoritma nosaukumā. 

14
00:00:38,970 --> 00:00:42,606
Tā vietā, lai domātu, mums ir viens
sešu elementu masīvs, domāsim, ka 

15
00:00:42,606 --> 00:00:46,243
mums ir seši viena elementa masīvi,
un tad vienkārši apvienosim tos 

16
00:00:46,243 --> 00:00:49,880
pareizā secībā un sapludināsim
kopā. 

17
00:00:49,880 --> 00:00:51,287
Tas būtu viens no veidiem, kā to
sakārtot.

18
00:00:51,287 --> 00:00:52,620
Un to dara sapludināšanas
kārtošana.

19
00:00:52,620 --> 00:00:55,755
Un tā izmanto kaut ko, ko sauc par
rekursiju, par ko mēs drīz runāsim 

20
00:00:55,755 --> 00:00:58,890
citā videoklipā. 

21
00:00:58,890 --> 00:01:02,526
Un, ja vēlaties iegūt labāku
izpratni par to, kā darbojas rekursija, 

22
00:01:02,526 --> 00:01:06,163
iespējams, vēlēsieties apskatīt to
videoklipu, pirms skatīsieties šo, 

23
00:01:06,163 --> 00:01:09,800
jo te diezgan daudz runāsim par
rekursiju. 

24
00:01:09,800 --> 00:01:12,275
Sapludināšanas kārtošana noteikti
ir vissarežģītākā no visiem četriem 

25
00:01:12,275 --> 00:01:14,750
kārtošanas veidiem, kurus mēs
aplūkojam šajā kursā. 

26
00:01:14,750 --> 00:01:17,720
Un tāpēc es iešu cauri šim nedaudz
lēnāk nekā pārējiem.

27
00:01:17,720 --> 00:01:19,956
Bet pašam sapludināšanas kārtošanas
algoritmam patiesībā ir diezgan 

28
00:01:19,956 --> 00:01:22,192
maz soļu. 

29
00:01:22,192 --> 00:01:26,311
Būtībā mēs teiksim: mēs kārtosim
masīva kreiso pusi, kārtosim masīva 

30
00:01:26,311 --> 00:01:30,430
labo pusi, un pēc tam sapludināsim
abas puses. 

31
00:01:30,430 --> 00:01:33,877
Tas būtībā ir sapludināšanas veids.

32
00:01:33,877 --> 00:01:37,709
Protams, praksē tas ir daudz
detalizētāks, bet tagad aplūkosim šo.

33
00:01:37,709 --> 00:01:40,099
Tātad, šeit ir tas pats sešu
elementu masīvs, kuru mēs visu laiku 

34
00:01:40,099 --> 00:01:42,490
esam kārtojuši. 

35
00:01:42,490 --> 00:01:46,065
Un mēs sāksim sekot mūsu pseidokoda
soļiem, proti, mēs vēlamies 

36
00:01:46,065 --> 00:01:49,640
sakārtot šī ķieģeļsarkanā masīva
kreiso pusi. 

37
00:01:49,640 --> 00:01:51,940
Tāpēc mēs pagaidām koncentrēsimies
tikai uz šo daļu.

38
00:01:51,940 --> 00:01:55,427
Un patiesībā, lai lietas būtu
nedaudz vienkāršākas, un tāpēc, ka šajā 

39
00:01:55,427 --> 00:01:58,915
videoklipā esmu krāsojis dažādas
lietas dažādos veidos, sākot ar šo 

40
00:01:58,915 --> 00:02:02,402
momentu, mēs sauksim šo kopējā
sarkanā masīva kreiso pusi par 

41
00:02:02,402 --> 00:02:05,890
purpursarkano masīva pusi. 

42
00:02:05,890 --> 00:02:07,120
Labi?

43
00:02:07,120 --> 00:02:09,970
Tātad mēs šobrīd esam masīva
kreisās puses kārtošanas procesā.

44
00:02:09,970 --> 00:02:12,200
Bet mēs nezinām, kā to izdarīt.

45
00:02:12,200 --> 00:02:14,600
Mēs nezinām, kā sakārtot masīva
kreiso pusi.

46
00:02:14,600 --> 00:02:16,030
Tātad, kāpēc mēs vienkārši
neatgriežamies pie sapludināšanas 

47
00:02:16,030 --> 00:02:17,460
kārtošanas darbībām? 

48
00:02:17,460 --> 00:02:18,944
Labi, ja es nezinu, kā kārtot
masīva kreiso pusi, es vienkārši sākšu 

49
00:02:18,944 --> 00:02:20,429
no jauna. 

50
00:02:20,429 --> 00:02:22,310
Kārtojiet šī masīva kreiso pusi.

51
00:02:22,310 --> 00:02:25,236
Tagad es vēlos koncentrēties tikai
uz šo masīva daļu, kreiso pusi.

52
00:02:25,236 --> 00:02:27,053
Un es kaut kā patvaļīgi nolemju, ka
mana kreisā puse būs mazāka par 

53
00:02:27,053 --> 00:02:28,870
labo pusi. 

54
00:02:28,870 --> 00:02:30,010
Man ir trīs elementi.

55
00:02:30,010 --> 00:02:31,140
Es nevaru tos sadalīt vienmērīgi.

56
00:02:31,140 --> 00:02:32,950
Man nevar būt viens un 1/2 elementi
katrā pusē.

57
00:02:32,950 --> 00:02:35,343
Tātad, kamēr es esmu konsekvents,
kamēr es vienmēr izvēlos, šajā 

58
00:02:35,343 --> 00:02:37,736
gadījumā kreisā puse ir mazāka, tas
derēs sapludināšanas kārtošanas 

59
00:02:37,736 --> 00:02:40,130
nolūkiem. 

60
00:02:40,130 --> 00:02:43,840
Tāpēc tagad man ir palicis šis
vienīgais elements, šis elements pieci.

61
00:02:43,840 --> 00:02:46,360
Kā kārtot viena elementa masīvu?

62
00:02:46,360 --> 00:02:49,270
Labas ziņas šeit ir tādas, ka man
tas nemaz nav jākārto.

63
00:02:49,270 --> 00:02:52,900
Viena elementa masīvs obligāti ir
jāsakārto.

64
00:02:52,900 --> 00:02:55,185
Tāpēc es varu teikt, ka, ja es
kārtoju purpursarkanās daļas kreiso 

65
00:02:55,185 --> 00:02:57,470
pusi, tā ir sakārtota. 

66
00:02:57,470 --> 00:03:00,770
Mēs to vienkārši nosauksim to par
sakārtotu un pagaidām atliksim malā.

67
00:03:00,770 --> 00:03:04,870
Tāpēc tagad es vēlos atgriezties
pie purpursarkanās daļas labajā pusē.

68
00:03:04,870 --> 00:03:07,150
Tā ir šī.

69
00:03:07,150 --> 00:03:10,750
Kā kārtot šo masīvu, šo
apakšmasīvu?

70
00:03:10,750 --> 00:03:12,490
Atgriezīsimies atpakaļ pie saviem
soļiem.

71
00:03:12,490 --> 00:03:14,680
Es gribu kārtot tikai kreiso pusi.

72
00:03:14,680 --> 00:03:15,820
Kreisajā pusē tagad ir divi.

73
00:03:15,820 --> 00:03:16,780
Tas ir viens elements.

74
00:03:16,780 --> 00:03:18,530
Es zinu, kā kārtot vienu elementu.

75
00:03:18,530 --> 00:03:21,900
Tāpēc es esmu sakārtojis šo kreiso
pusi, purpursarkanās daļas labās 

76
00:03:21,900 --> 00:03:25,270
puses kreiso pusi. 

77
00:03:25,270 --> 00:03:26,480
Re, kur mēs esam.

78
00:03:26,480 --> 00:03:27,580
Tas ir sakārtots.

79
00:03:27,580 --> 00:03:30,290
Tagad es atgriežos un kārtoju
purpursarkanās kreisās puses labo pusi, 

80
00:03:30,290 --> 00:03:33,001
kas ir viens. 

81
00:03:33,001 --> 00:03:34,000
Viens ir viens elements.

82
00:03:34,000 --> 00:03:35,041
To ir patiešām viegli sakārtot.

83
00:03:35,041 --> 00:03:36,910
Tas ir sakārtotā pozīcijā.

84
00:03:36,910 --> 00:03:39,570
Tagad ir pirmā reize, kad beidzot
tieku pie šīs sapludināšanas 

85
00:03:39,570 --> 00:03:42,230
kārtošanas trešā posma, kurā es
sapludinu abas puses kopā. 

86
00:03:42,230 --> 00:03:46,750
Tātad, šeit man ir jāņem vērā šīs
divas gaiši zaļās pusītes.

87
00:03:46,750 --> 00:03:51,850
Un man ir jāizlemj, kurai ir zemāks
elements.

88
00:03:51,850 --> 00:03:53,990
Šajā gadījumā tas ir viens.

89
00:03:53,990 --> 00:03:56,940
Tāpēc es paņemu vienu un ievietoju
to kāda jaunā hipotētiskā masīva 

90
00:03:56,940 --> 00:03:59,890
pirmajā pozīcijā. 

91
00:03:59,890 --> 00:04:03,820
Tad es salīdzinu abus ar neko un
jautāju, kurš no tiem ir zemāks.

92
00:04:03,820 --> 00:04:04,750
Nu, divi vai nekas.

93
00:04:04,750 --> 00:04:06,970
Kas ir zemāks, tas ir divi.

94
00:04:06,970 --> 00:04:10,480
Tātad tagad pārkadrēsim attēlu, jo,
ja atceramies rekursiju, mēs 

95
00:04:10,480 --> 00:04:13,990
koncentrējāmies tikai uz
kieģeļsarkanā masīva kreiso pusi, ko tad 

96
00:04:13,990 --> 00:04:17,500
saucām par purpursarkano masīvu. 

97
00:04:17,500 --> 00:04:20,735
Šajā posmā esam sakārtojuši
purpursarkanā masīva kreiso pusi, kas ir 

98
00:04:20,735 --> 00:04:23,970
pieci, un labo pusi, kas sākotnēji
bija divi un viens, bet tagad esam 

99
00:04:23,970 --> 00:04:27,205
veikuši šīs sapludināšanas darbības
un esam to izdarījuši pareizā 

100
00:04:27,205 --> 00:04:30,440
secībā. 

101
00:04:30,440 --> 00:04:34,455
Tātad tagad esam trešajā darbības
posmā, jo mēs jau esam sakārtojuši 

102
00:04:34,455 --> 00:04:38,470
purpursarkanā masīva kreiso pusi un
purpursarkanā masīva labo pusi. 

103
00:04:38,470 --> 00:04:41,890
Tāpēc tagad mums ir jāsapludina šīs
divas puses.

104
00:04:41,890 --> 00:04:45,235
Un tāpat kā darījām pirms brīža ar
divi un viens, mēs salīdzināsim 

105
00:04:45,235 --> 00:04:48,580
kreisās daļas pirmo elementu un
labās daļas pirmo elementu, 

106
00:04:48,580 --> 00:04:51,925
noskaidrosim, kurš no tiem ir
mazāks, un padarīsim to par mūsu jauna 

107
00:04:51,925 --> 00:04:55,270
masīva pirmo elementu. 

108
00:04:55,270 --> 00:04:57,927
Tāpēc es salīdzinu pieci un viens.

109
00:04:57,927 --> 00:04:59,260
Un es saku, kurš ir mazāks?

110
00:04:59,260 --> 00:05:01,945
Nu, tas ir viens, tāpēc viens kļūst
par pirmo šī jaunā trīs elementu 

111
00:05:01,945 --> 00:05:04,630
masīva elementu. 

112
00:05:04,630 --> 00:05:06,130
Tagad man jāpieņem cits lēmums.

113
00:05:06,130 --> 00:05:09,310
Pieci ir zemāks vai divi ir zemāks?

114
00:05:09,310 --> 00:05:10,240
Nu divi ir zemāks.

115
00:05:10,240 --> 00:05:14,560
Tātad divi kļūst par nākamo mūsu
sapludināšanas soļa elementu.

116
00:05:14,560 --> 00:05:17,980
Tad es saku, vai pieci ir zemāks
vai nekas ir zemāks?

117
00:05:17,980 --> 00:05:21,280
Skaidrs, ka šajā gadījumā vienīgais
variants, kas man paliek ir pieci.

118
00:05:21,280 --> 00:05:24,205
Un tāpēc tagad, šajā momentā, atkal
rekursīvi domāsim par to, kur mēs 

119
00:05:24,205 --> 00:05:27,130
atrodamies. 

120
00:05:27,130 --> 00:05:29,710
Mēs esam sakārtojuši visu sarkano
masīvu, esam veikuši tikai pirmo 

121
00:05:29,710 --> 00:05:32,290
darbību. 

122
00:05:32,290 --> 00:05:34,810
Mēs esam sakārtojuši kreiso daļu.

123
00:05:34,810 --> 00:05:37,885
Mēs to darījām rekursīvi, bet esam
sakārtojuši kopējā sarkanā masīva 

124
00:05:37,885 --> 00:05:40,960
kreiso daļu. 

125
00:05:40,960 --> 00:05:43,753
Līdz ar to mēs varam to pagaidām
atstāt malā, jo tagad mums ir 

126
00:05:43,753 --> 00:05:46,546
jādodas uz sapludināšanas
kārtošanas procesa nākamo soli, proti, 

127
00:05:46,546 --> 00:05:49,340
jākārto sarkanā masīva labā puse. 

128
00:05:49,340 --> 00:05:51,381
Tātad pāriesim un koncentrēsimies
uz labo pusi.

129
00:05:51,381 --> 00:05:53,495
Mēs veiksim tieši tās pašas
darbības, kuras tikko veicām ar kreiso 

130
00:05:53,495 --> 00:05:55,610
daļu. 

131
00:05:55,610 --> 00:05:58,990
Bet tagad mēs to darīsim ar šo
sarkano daļu labajā pusē.

132
00:05:58,990 --> 00:06:01,649
Tāpēc es vēlos sakārtot šī masīva
kreiso pusi.

133
00:06:01,649 --> 00:06:02,690
Nu, tas ir diezgan vienkārši.

134
00:06:02,690 --> 00:06:04,369
Es vienkārši patvaļīgi atkal to
sadalu.

135
00:06:04,369 --> 00:06:04,910
Es skatos uz to.

136
00:06:04,910 --> 00:06:07,057
Es saku: labi, trīs ir viens
elements.

137
00:06:07,057 --> 00:06:08,723
Viens elements jau ir sakārtots,
tāpēc man nekas nav jādara, kas ir 

138
00:06:08,723 --> 00:06:10,389
lieliski. 

139
00:06:10,389 --> 00:06:13,060
Es varu vienkārši atstāt to malā un
teikt, ka trīs jau ir sakārtots.

140
00:06:13,060 --> 00:06:16,501
Tagad es gribu sakārtot labo pusi
no ne tik ķieģeļsarkanās, bet 

141
00:06:16,501 --> 00:06:19,942
joprojām sarkanās masīva puses, kas
ir šī daļa. 

142
00:06:19,942 --> 00:06:20,650
Kā to izdarīt?

143
00:06:20,650 --> 00:06:21,980
Nu, tas ir vairāk nekā viens
elements.

144
00:06:21,980 --> 00:06:24,521
Tāpēc es atkal atgriezīšos pie sava
procesa sākuma.

145
00:06:24,521 --> 00:06:26,450
Es kārtošu šī masīva kreiso pusi.

146
00:06:26,450 --> 00:06:28,420
Tad es paskatos un saku, lūk,
kreisā puse.

147
00:06:28,420 --> 00:06:28,930
Tas ir seši.

148
00:06:28,930 --> 00:06:30,190
Tas jau ir sakārtots.

149
00:06:30,190 --> 00:06:32,500
Tagad es kārtošu masīva labo pusi.

150
00:06:32,500 --> 00:06:33,250
Tas ir četri.

151
00:06:33,250 --> 00:06:34,392
Tas jau ir sakārtots.

152
00:06:34,392 --> 00:06:36,491
Tagad es atkal nonāku pie
sapludināšanas posma, kur man atkal ir 

153
00:06:36,491 --> 00:06:38,590
jāveic šāda veida salīdzinājumi. 

154
00:06:38,590 --> 00:06:39,730
Kurš ir zemāks?

155
00:06:39,730 --> 00:06:42,041
Seši ir zemāks vai četri ir zemāks?

156
00:06:42,041 --> 00:06:44,464
Nu, četri ir zemāks, tāpēc tas
kļūst par mūsu jaunā sapludināta mazā 

157
00:06:44,464 --> 00:06:46,887
apakšmasīva pirmo elementu. 

158
00:06:46,887 --> 00:06:48,970
Un tad man ir jāizvēlas starp seši
un neko.

159
00:06:48,970 --> 00:06:51,640
Un es saku, seši ir mazākais
atlikušais.

160
00:06:51,640 --> 00:06:56,080
Tāpēc tagad esmu sakārtojis labās
puses kreiso pusi.

161
00:06:56,080 --> 00:06:59,470
Un es esmu sakārtojis labās puses
labo pusi.

162
00:06:59,470 --> 00:07:03,470
Tāpēc tagad es vēlos sapludināt šīs
divas daļas.

163
00:07:03,470 --> 00:07:07,860
Un atkal mēs veiksim tieši to pašu
procesu, ko veicām ar kreiso daļu.

164
00:07:07,860 --> 00:07:10,370
Es teikšu, trīs ir zemāks vai
četri?

165
00:07:10,370 --> 00:07:12,020
Nu, tas ir trīs.

166
00:07:12,020 --> 00:07:14,559
Un tad es teikšu, četri ir zemāks,
vai nekas?

167
00:07:14,559 --> 00:07:17,669
Kreisajā pusē nekas nav palicis,
tad man jāzina, ka visam labajā pusē 

168
00:07:17,669 --> 00:07:20,780
ir jābūt lielākam par visu, kas
šobrīd ir sapludinātajā masīvā. 

169
00:07:20,780 --> 00:07:23,840
Tāpēc tā vietā, lai teiktu: Labi,
es ielikšu četri un tad seši, jo 

170
00:07:23,840 --> 00:07:26,900
tikai tie ir palikuši vienā pusē,
visam ir jāiet. 

171
00:07:26,900 --> 00:07:29,220
Tātad viss nokrīt.

172
00:07:29,220 --> 00:07:32,300
Un atkal padomāsim par to, kur
esam.

173
00:07:32,300 --> 00:07:35,660
Šajā brīdī sākotnējam
ķieģeļsarkanajam masīvam, ar kuru mēs sākām, 

174
00:07:35,660 --> 00:07:39,020
esam veikuši divas mūsu pseidokoda
darbības. 

175
00:07:39,020 --> 00:07:42,860
Mēs esam sakārtojuši kopējā
ķieģeļsarkanā masīva kreiso pusi.

176
00:07:42,860 --> 00:07:46,250
Un mēs esam sakārtojuši šī kopējā
ķieģeļsarkanā masīva labo pusi.

177
00:07:46,250 --> 00:07:50,750
Un tagad pēdējais, kas mums jādara,
ir sapludināt šīs divas puses.

178
00:07:50,750 --> 00:07:55,430
Un tāpat kā iepriekš, mēs atkal
turpinām uzdot sev to pašu jautājumu.

179
00:07:55,430 --> 00:07:58,377
Kas ir zemāks, viens vai trīs?

180
00:07:58,377 --> 00:08:00,368
Ievērojiet mazo melno līniju, kas
sadala abas puses, lai padarītu to 

181
00:08:00,368 --> 00:08:02,360
vizuāli skaidrāku. 

182
00:08:02,360 --> 00:08:04,960
Kas ir zemāks, viens vai trīs?

183
00:08:04,960 --> 00:08:06,320
Nu, viens.

184
00:08:06,320 --> 00:08:10,220
Tagad atkal uzdodu sev jautājumu,
kas ir zemāks, divi vai trīs?

185
00:08:10,220 --> 00:08:11,840
Tas būtu divi.

186
00:08:11,840 --> 00:08:14,820
Kas ir zemāks, pieci vai trīs?

187
00:08:14,820 --> 00:08:16,270
Tas ir trīs.

188
00:08:16,270 --> 00:08:17,570
Pieci vai četri?

189
00:08:17,570 --> 00:08:18,790
Tas ir četri.

190
00:08:18,790 --> 00:08:20,110
Pieci vai seši.

191
00:08:20,110 --> 00:08:21,880
Tas ir pieci.

192
00:08:21,880 --> 00:08:23,660
Seši vai nekas?

193
00:08:23,660 --> 00:08:24,621
Tas ir seši.

194
00:08:24,621 --> 00:08:27,937
Un tāpēc, veicot šo procesu
rekursīvi un sadalot savu problēmu 

195
00:08:27,937 --> 00:08:31,253
mazākos un mazākos apakšmasīvos,
kārtojot tos, sapludinot tos kopā, 

196
00:08:31,253 --> 00:08:34,570
pēc vairākām darbībām esmu
pabeidzis savu kārtošanu. 

197
00:08:34,570 --> 00:08:36,840
Un man te viss ir sakārtots tumši
zilā krāsā.

198
00:08:36,840 --> 00:08:39,580
Viens, divi, trīs, četri, pieci,
seši.

199
00:08:39,580 --> 00:08:42,610
Tas ne vienmēr ir tik vienkārši kā
burbuļa kārtošana, ievietošanas 

200
00:08:42,610 --> 00:08:45,640
kārtošana vai atlases kārtošana. 

201
00:08:45,640 --> 00:08:47,680
Bet vai šeit ir kādas
priekšrocības?

202
00:08:47,680 --> 00:08:50,530
Nu, atbilde ir - jā, ir.

203
00:08:50,530 --> 00:08:54,520
Sliktākajā gadījumā mums ir
jāsadala n elementi.

204
00:08:54,520 --> 00:08:57,295
Un tad mums tie ir jāpārkombinē,
efektīvi dubultojot sakārtotos 

205
00:08:57,295 --> 00:09:00,070
masīvus, veidojot tos. 

206
00:09:00,070 --> 00:09:01,632
Tātad mēs ņemam divus viena
elementa masīvus un pārvēršam tos par 

207
00:09:01,632 --> 00:09:03,194
divu elementu masīvu. 

208
00:09:03,194 --> 00:09:05,309
Mēs ņemam divus divu elementu
masīvus.

209
00:09:05,309 --> 00:09:06,850
Mēs pārveidojam tos četru elementu
masīvā.

210
00:09:06,850 --> 00:09:09,160
Un tā tālāk, un tā tālāk, un tā
tālāk.

211
00:09:09,160 --> 00:09:12,220
Labākajā gadījumā, piemēram,
atlases kārtošana, masīvs jau ir 

212
00:09:12,220 --> 00:09:15,280
sakārtots, bet mēs to nezinām. 

213
00:09:15,280 --> 00:09:16,600
Mēs to nezinām, kamēr mēs to
nesadalām un atkal apvienojam ar šo 

214
00:09:16,600 --> 00:09:17,920
algoritmu. 

215
00:09:17,920 --> 00:09:21,010
Šeit nav nekāda veida saīsnes,
izņemot iepriekšēju meklēšanu.

216
00:09:21,010 --> 00:09:23,920
Bet tas arī papildinās papildu
laiku.

217
00:09:23,920 --> 00:09:27,625
Tātad rezultāts ir tāds, ka mums ir
n elementi — un, iespējams, mums 

218
00:09:27,625 --> 00:09:31,330
tie ir jāapvieno, ja mēs
dubultojam — log n reizes. 

219
00:09:31,330 --> 00:09:32,860
Matemātiski tas darbojas šādi.

220
00:09:32,860 --> 00:09:37,170
Tātad patiesībā, atšķirībā no
citiem apskatītajiem algoritmiem, 

221
00:09:37,170 --> 00:09:41,480
sliktākajā gadījumā sapludināšanas
kārtošanas izpildes laiks ir O no 

222
00:09:41,480 --> 00:09:45,790
n log n, kas kopumā būs mazāks vai
ātrāks par n kvadrātā. 

223
00:09:45,790 --> 00:09:48,445
Labākajā gadījumā tas joprojām ir n
log n, jo mums vēl ir jāiziet šis 

224
00:09:48,445 --> 00:09:51,100
process vēlreiz. 

225
00:09:51,100 --> 00:09:53,699
Tātad labākajā gadījumā tas var būt
lēnāks nekā, piemēram, burbuļa 

226
00:09:53,699 --> 00:09:56,299
kārtošana, kur masīvs ir lieliski
sakārtots. 

227
00:09:56,299 --> 00:10:00,190
Kā jūs atceraties omega, tur ir n,
nevis n log n.

228
00:10:00,190 --> 00:10:03,182
Bet sliktākajā gadījumā vai varbūt
pat ierastajā gadījumā 

229
00:10:03,182 --> 00:10:06,175
sapludināšanas kārtošana faktiski
būs ātrāka, iespējams, aizņemot 

230
00:10:06,175 --> 00:10:09,167
vairāk atmiņas, jo mums ir
jāpārkombinē un jāveido mūsu apakšmasīviem 

231
00:10:09,167 --> 00:10:12,160
jauni segmenti atmiņā. 

232
00:10:12,160 --> 00:10:15,506
Tātad sapludināšanas kārtošana ir
patiešām jaudīgs rīks, kas 

233
00:10:15,506 --> 00:10:18,853
jāiekļauj jūsu rīklodziņā, tiklīdz
jūs saprotat rekursiju, jo tas var 

234
00:10:18,853 --> 00:10:22,200
paātrināt masīva kārtošanas
procesu. 

235
00:10:22,200 --> 00:10:23,290
Mani sauc Dags Loids.

236
00:10:23,290 --> 00:10:25,400
Šis ir CS50.