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

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, deci o îmbinare
fel este încă un alt algoritm

4
00:00:08,460 --> 00:00:11,200
pe care le putem folosi pentru a rezolva
elementele unei matrice.

5
00:00:11,200 --> 00:00:14,480
Dar, așa cum vom vedea, are o
diferență foarte fundamentală

6
00:00:14,480 --> 00:00:17,850
de la selecție fel, cu bule
sortare, și sortare prin inserție

7
00:00:17,850 --> 00:00:20,280
care fac într-adevăr destul de inteligent.

8
00:00:20,280 --> 00:00:24,290
>> Ideea de bază merge
fel este de a sorta tablouri mai mici

9
00:00:24,290 --> 00:00:27,430
și apoi combină aceste tablouri
împreună, sau fuziona them--

10
00:00:27,430 --> 00:00:31,440
prin urmare, name-- în ordine sortată.

11
00:00:31,440 --> 00:00:34,230
Modul în care merge sort face
acest lucru este prin folosirea un instrument

12
00:00:34,230 --> 00:00:37,290
numit recursivitate, care este ceea ce
vom vorbi despre curând,

13
00:00:37,290 --> 00:00:39,720
dar nu am cu adevărat vorbit despre încă.

14
00:00:39,720 --> 00:00:43,010
>> Iată ideea de bază din spatele merge sort.

15
00:00:43,010 --> 00:00:46,320
Sorta jumătatea stângă a matrice,
presupunând n este mai mare decât 1.

16
00:00:46,320 --> 00:00:49,980
Și ce vreau să spun când spun
presupunând n este mai mare decât 1 este,

17
00:00:49,980 --> 00:00:53,970
Cred că putem fi de acord că, dacă o serie
doar constă dintr-un singur element,

18
00:00:53,970 --> 00:00:54,680
e sortate.

19
00:00:54,680 --> 00:00:56,560
Noi de fapt nu au nevoie de
a face ceva la ea.

20
00:00:56,560 --> 00:00:58,059
Putem declara doar să fie sortate.

21
00:00:58,059 --> 00:01:00,110
E doar un singur element.

22
00:01:00,110 --> 00:01:03,610
>> Deci Pseudocodul, din nou, este
sorta jumătatea stângă a matrice,

23
00:01:03,610 --> 00:01:08,590
apoi sorta jumătatea dreaptă matrice,
apoi îmbinați cele două jumătăți împreună.

24
00:01:08,590 --> 00:01:11,040
Acum, s-ar putea să fie deja
gândire, un fel de doar

25
00:01:11,040 --> 00:01:14,080
Sună ca și cum ai pune pe the--
nu faci de fapt nimic.

26
00:01:14,080 --> 00:01:16,330
Vrei să spui că sorta stânga
jumătate, sorta jumătatea din dreapta,

27
00:01:16,330 --> 00:01:19,335
dar nu spui
mi cum o faci.

28
00:01:19,335 --> 00:01:22,220
>> Dar amintiți-vă că, atâta timp cât
o matrice este un singur element,

29
00:01:22,220 --> 00:01:23,705
putem declare sortate.

30
00:01:23,705 --> 00:01:25,330
Atunci putem combina doar le împreună.

31
00:01:25,330 --> 00:01:27,788
Și asta e de fapt
Ideea fundamentală din spatele merge sort,

32
00:01:27,788 --> 00:01:31,150
este să-l rupe în jos, astfel încât
tablouri tale sunt de dimensiuni unul.

33
00:01:31,150 --> 00:01:33,430
Și apoi reconstrui de acolo.

34
00:01:33,430 --> 00:01:35,910
>> Merge fel este cu siguranta
un algoritm complicat.

35
00:01:35,910 --> 00:01:38,210
Și este, de asemenea, un pic
complicat de a vizualiza.

36
00:01:38,210 --> 00:01:41,870
Deci, sperăm, vizualizarea pe care am
avem aici va ajuta să urmați de-a lungul.

37
00:01:41,870 --> 00:01:45,640
Și voi încerca meu cel mai bun pentru a relata lucrurile
și să treacă prin acest lucru un pic mai mult

38
00:01:45,640 --> 00:01:49,180
încet decât celelalte
doar pentru a obține, sperăm cap

39
00:01:49,180 --> 00:01:51,800
în jurul valorii de ideile din spatele merge sort.

40
00:01:51,800 --> 00:01:54,680
>> Deci avem aceeași matrice ca
alte sortare videoclipuri algoritm

41
00:01:54,680 --> 00:01:57,120
dacă ați văzut them--
o gamă de șase element de.

42
00:01:57,120 --> 00:02:02,110
Și codul pseudocod aici este un fel
jumătatea din stânga, sorta jumătatea din dreapta,

43
00:02:02,110 --> 00:02:03,890
fuziona cele două jumătăți împreună.

44
00:02:03,890 --> 00:02:09,770
Așa că haideți să ia acest rosu foarte inchis cărămidă
matrice și sorta jumătatea stângă a acestuia.

45
00:02:09,770 --> 00:02:13,380
>> Deci, pentru moment, vom
să ignore lucrurile pe dreapta.

46
00:02:13,380 --> 00:02:15,740
E acolo, dar suntem
nu la acest pas încă.

47
00:02:15,740 --> 00:02:18,220
Nu suntem la fel
jumătate din dreapta a matrice.

48
00:02:18,220 --> 00:02:21,037
Suntem la fel stânga
jumătate din matrice.

49
00:02:21,037 --> 00:02:22,870
Și doar de dragul
de a fi un pic mai mult

50
00:02:22,870 --> 00:02:26,480
clar, așa că am putea referi
la ceea ce pas suntem pe,

51
00:02:26,480 --> 00:02:29,800
Mă duc pentru a comuta
Culoarea de acest set la portocaliu.

52
00:02:29,800 --> 00:02:33,190
Acum, suntem încă vorbesc despre
același jumătatea stângă a șirului original.

53
00:02:33,190 --> 00:02:38,520
Dar eu sunt în speranța că prin posibilitatea de a
se referă la culorile diverse articole,

54
00:02:38,520 --> 00:02:40,900
acesta va face un pic mai mult
clar ce se întâmplă aici.

55
00:02:40,900 --> 00:02:43,270
>> OK, asa ca acum avem un
trei matrice elemente.

56
00:02:43,270 --> 00:02:46,420
Cum putem sorta jumătatea stângă a acestei
matrice, care este încă acest pas?

57
00:02:46,420 --> 00:02:49,400
Încercăm să sorta stânga
jumătate din array-- roșu de cărămidă

58
00:02:49,400 --> 00:02:52,410
din care jumătatea stângă
Acum am colorat portocaliu.

59
00:02:52,410 --> 00:02:54,840
>> Ei bine, am putea încerca și
repetați din nou acest proces.

60
00:02:54,840 --> 00:02:56,756
Deci suntem încă în
mijloc de a încerca de a sorta

61
00:02:56,756 --> 00:02:58,700
jumătatea stângă a tabloului complet.

62
00:02:58,700 --> 00:03:00,450
Jumătatea stângă a
matrice, Mă duc

63
00:03:00,450 --> 00:03:03,910
pentru a decide în mod arbitrar că jumătatea stângă
va fi mai mică decât jumătatea din dreapta,

64
00:03:03,910 --> 00:03:06,550
deoarece acest lucru se întâmplă pentru a
constau din trei elemente.

65
00:03:06,550 --> 00:03:11,260
>> Și așa am de gând să spun că
jumătate din stânga a jumătatea stângă matrice

66
00:03:11,260 --> 00:03:14,050
este doar elementul cinci.

67
00:03:14,050 --> 00:03:18,360
Cinci, fiind un singur element
matrice, știm cum să-l rezolve.

68
00:03:18,360 --> 00:03:21,615
Și astfel cinci este sortată.

69
00:03:21,615 --> 00:03:22,990
Noi doar o să declare că.

70
00:03:22,990 --> 00:03:24,890
Este un singur element de matrice.

71
00:03:24,890 --> 00:03:29,015
>> Deci ne-am sortat acum
jumătatea stângă a half-- stânga

72
00:03:29,015 --> 00:03:33,190
sau mai degrabă, am sortează
jumătatea stângă a Orange.

73
00:03:33,190 --> 00:03:37,970
Deci, acum, în scopul de a încă complet
jumătate stânga matrice generală, a

74
00:03:37,970 --> 00:03:43,481
avem nevoie pentru a sorta jumătatea din dreapta
de portocaliu, sau chestia asta.

75
00:03:43,481 --> 00:03:44,230
Cum facem asta?

76
00:03:44,230 --> 00:03:45,930
Ei bine, avem o gamă de două elemente.

77
00:03:45,930 --> 00:03:50,470
Deci, putem sorta jumătatea stângă
de matrice, care este de două.

78
00:03:50,470 --> 00:03:52,090
Doi este un singur element.

79
00:03:52,090 --> 00:03:55,890
Deci, este sortate în mod implicit.
Apoi, putem sorta jumătatea din dreapta

80
00:03:55,890 --> 00:03:58,530
acelei porțiuni din matrice, cea.

81
00:03:58,530 --> 00:04:00,210
Asta e un fel de mod implicit.

82
00:04:00,210 --> 00:04:03,610
>> Aceasta este acum pentru prima dată
am ajuns un pas merge.

83
00:04:03,610 --> 00:04:06,135
Am finalizat, deși
suntem acum un fel de imbricate down--

84
00:04:06,135 --> 00:04:08,420
și asta e un fel de complicat
lucru cu recursivitate este,

85
00:04:08,420 --> 00:04:10,930
aveți nevoie pentru a vă menține
cap despre unde suntem.

86
00:04:10,930 --> 00:04:15,560
Deci, ne-am un fel de stânga
jumătate din porțiunea portocaliu.

87
00:04:15,560 --> 00:04:21,280
>> Și acum, suntem în mijlocul de sortare
jumătatea dreaptă a porțiunii portocaliu.

88
00:04:21,280 --> 00:04:25,320
Și în acest proces, suntem
acum pe cale de a fi pe treapta,

89
00:04:25,320 --> 00:04:27,850
fuziona cele două jumătăți împreună.

90
00:04:27,850 --> 00:04:31,700
Când ne uităm la cele două jumătăți
de matrice, vedem două și unul.

91
00:04:31,700 --> 00:04:33,880
Care element este mai mic?

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

93
00:04:35,160 --> 00:04:36,760
>> Atunci care elementul este mai mic?

94
00:04:36,760 --> 00:04:38,300
Ei bine, e două sau nimic.

95
00:04:38,300 --> 00:04:39,910
Deci e doi.

96
00:04:39,910 --> 00:04:43,690
Deci, acum, doar pentru a încadra din nou
unde suntem în context,

97
00:04:43,690 --> 00:04:48,230
am sortează
jumătatea stângă a portocaliu

98
00:04:48,230 --> 00:04:49,886
și jumătatea dreaptă a originii.

99
00:04:49,886 --> 00:04:52,510
Știu că am schimbat culorile
din nou, dar asta e în cazul în care am fost.

100
00:04:52,510 --> 00:04:54,676
Și motivul pentru care am făcut acest lucru
se datorează faptului că acest proces este

101
00:04:54,676 --> 00:04:57,870
O să continui, iterarea jos.

102
00:04:57,870 --> 00:05:00,500
Am sortat stânga
jumătate din fosta portocaliu

103
00:05:00,500 --> 00:05:02,590
și jumătatea dreaptă a fostului portocaliu.

104
00:05:02,590 --> 00:05:05,620
>> Acum, avem nevoie pentru a fuziona cele
două jumătăți împreună prea.

105
00:05:05,620 --> 00:05:07,730
Acesta este pasul suntem pe.

106
00:05:07,730 --> 00:05:11,440
Deci, avem în vedere cele de mai
elemente care sunt acum verde,

107
00:05:11,440 --> 00:05:12,972
jumătatea stângă a șirului original.

108
00:05:12,972 --> 00:05:14,680
Și am merge pe cei
utilizând același proces

109
00:05:14,680 --> 00:05:18,660
am facut-o pentru fuzionarea două
și acum o doar un moment.

110
00:05:18,660 --> 00:05:23,080
>> Jumătatea din stânga, cel mai mic
element de pe jumătatea stângă este de cinci.

111
00:05:23,080 --> 00:05:25,620
Cel mai mic element constitutiv al
jumătatea dreaptă este una.

112
00:05:25,620 --> 00:05:27,370
Care dintre cei este mai mic?

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

114
00:05:29,260 --> 00:05:32,250
>> Cel mai mic element constitutiv al
jumătatea stângă este de cinci.

115
00:05:32,250 --> 00:05:35,540
Cel mai mic element constitutiv al
jumătatea dreaptă este de două.

116
00:05:35,540 --> 00:05:36,970
Care este cel mai mic?

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

118
00:05:38,160 --> 00:05:41,540
Și apoi în cele din urmă de cinci și
nimic, putem spune de cinci.

119
00:05:41,540 --> 00:05:43,935
>> OK, imagine atât de mare, să
ia o pauză pentru un al doilea

120
00:05:43,935 --> 00:05:46,080
și dau seama unde suntem.

121
00:05:46,080 --> 00:05:48,580
Dacă am pornit de la
Încă de la început, ne-am

122
00:05:48,580 --> 00:05:51,640
au încheiat acum pentru
matrice de ansamblu doar

123
00:05:51,640 --> 00:05:53,810
un pas de cod pseudocod aici.

124
00:05:53,810 --> 00:05:56,645
Am sortează
jumătatea stângă a tabloului.

125
00:05:56,645 --> 00:05:59,490
>> Amintiți-vă că originalul
comanda a fost cinci, doi, unu.

126
00:05:59,490 --> 00:06:02,570
Trecând prin acest proces
și cuiburi în jos și se repetă,

127
00:06:02,570 --> 00:06:05,990
continuând să rupă problema
jos în bucăți mai mici și mai mici,

128
00:06:05,990 --> 00:06:09,670
am finalizat acum
pas unul din pseudocod

129
00:06:09,670 --> 00:06:13,940
pentru întreaga matrice de pornire.

130
00:06:13,940 --> 00:06:16,670
Am sortat jumătate stângă.

131
00:06:16,670 --> 00:06:18,670
>> Deci, acum hai să înghețe acolo.

132
00:06:18,670 --> 00:06:23,087
Și acum să sorteze dreapta
jumătate din matrice originale.

133
00:06:23,087 --> 00:06:25,670
Și am de gând să fac asta de
trece prin același iterativ

134
00:06:25,670 --> 00:06:30,630
proces de rupere jos lucruri
și apoi fuzionarea lor împreună.

135
00:06:30,630 --> 00:06:34,290
>> Deci, jumătatea stângă a
roșu, sau jumătatea stângă

136
00:06:34,290 --> 00:06:38,830
din jumătatea dreaptă a originalului
matrice, am de gând să spun este de trei.

137
00:06:38,830 --> 00:06:40,312
Din nou, am fi consecvent aici.

138
00:06:40,312 --> 00:06:42,020
Dacă aveți un ciudat
Numărul de elemente ea,

139
00:06:42,020 --> 00:06:44,478
Nu contează cu adevărat dacă
faci cel mai mic din stânga

140
00:06:44,478 --> 00:06:45,620
sau cel din dreapta mai mici.

141
00:06:45,620 --> 00:06:49,230
>> Ceea ce contează este că ori de câte ori
întâlniți această problemă în desfășurarea

142
00:06:49,230 --> 00:06:51,422
a merge, trebuie să fie în concordanță.

143
00:06:51,422 --> 00:06:53,505
Ori nevoie întotdeauna să
face o partea stângă mai mic

144
00:06:53,505 --> 00:06:55,421
sau întotdeauna nevoie pentru a face
partea dreapta mai mici.

145
00:06:55,421 --> 00:06:57,720
Aici, am ales să întotdeauna
face partea din stânga mic

146
00:06:57,720 --> 00:07:04,380
când matrice meu, sau meu
sub-matrice, este de o dimensiune ciudat.

147
00:07:04,380 --> 00:07:07,420
>> Trei este un singur element,
Și așa este sortate.

148
00:07:07,420 --> 00:07:10,860
Am indatorare ca ipoteză
de-a lungul întregii noastre proces de până acum.

149
00:07:10,860 --> 00:07:15,020
Deci, acum să sorteze dreapta
jumătate din jumătatea din dreapta,

150
00:07:15,020 --> 00:07:18,210
sau jumătatea dreaptă a roșu.

151
00:07:18,210 --> 00:07:20,390
>> Din nou, avem nevoie de a împărți această jos.

152
00:07:20,390 --> 00:07:21,910
Acesta nu este un singur element de matrice.

153
00:07:21,910 --> 00:07:23,970
Nu putem declare sortate.

154
00:07:23,970 --> 00:07:27,060
Și astfel în primul rând, vom
pentru a sorta jumătatea stângă.

155
00:07:27,060 --> 00:07:31,620
>> Jumătatea din stânga este un singur element,
așa că este un fel de mod implicit.

156
00:07:31,620 --> 00:07:34,840
Apoi vom sorta dreapta
jumătate, care este un singur element.

157
00:07:34,840 --> 00:07:41,250
Este sortate în mod implicit. Si acum,
putem merge pe cei doi împreună.

158
00:07:41,250 --> 00:07:45,820
Patru este mai mic, și
apoi din șase este mai mică.

159
00:07:45,820 --> 00:07:48,870
>> Din nou, ceea ce am făcut în acest moment?

160
00:07:48,870 --> 00:07:52,512
Am sortat stânga
jumătate din jumătatea din dreapta.

161
00:07:52,512 --> 00:07:54,720
Sau de a merge inapoi la original
culori care au fost acolo,

162
00:07:54,720 --> 00:07:57,875
am sortat stânga
jumătate din roșu moale.

163
00:07:57,875 --> 00:08:00,416
Aceasta a fost inițial o cărămidă întuneric
roșu și acum e un roșu mai moale,

164
00:08:00,416 --> 00:08:02,350
sau a fost un roșu mai moale.

165
00:08:02,350 --> 00:08:05,145
>> Și apoi am sortează
jumătatea dreaptă a roșu moale.

166
00:08:05,145 --> 00:08:08,270
Acum, ei bine, sunt verde din nou, doar
pentru că mergem printr-un proces.

167
00:08:08,270 --> 00:08:10,720
Și noi trebuie să repete
acest peste si peste.

168
00:08:10,720 --> 00:08:14,695
>> Deci, acum putem merge pe cei
două jumătăți împreună.

169
00:08:14,695 --> 00:08:15,820
Și asta e ceea ce facem noi aici.

170
00:08:15,820 --> 00:08:17,653
Deci linia neagră doar
împărțit jumătatea stângă

171
00:08:17,653 --> 00:08:19,690
și jumătatea dreaptă a acestei părți fel.

172
00:08:19,690 --> 00:08:24,310
>> Vom compara mai mică valoare
pe partea stângă a array--

173
00:08:24,310 --> 00:08:26,710
sau scuză-mă, cel mai mic
Valoarea de jumătatea stângă

174
00:08:26,710 --> 00:08:30,790
la cea mai mică valoare a dreptului
jumătate și pentru a găsi că trei este mai mică.

175
00:08:30,790 --> 00:08:32,530
Și acum un pic de o optimizare, nu?

176
00:08:32,530 --> 00:08:35,175
Nu e de fapt nimic
stânga pe partea stângă.

177
00:08:35,175 --> 00:08:37,440
>> Nu e nimic rămas
pe partea stanga,

178
00:08:37,440 --> 00:08:40,877
astfel încât să putem eficient
doar move-- putem declara

179
00:08:40,877 --> 00:08:42,960
restul de acesta este de fapt
sortati si doar tac

180
00:08:42,960 --> 00:08:45,126
pe, pentru că nu e nimic
altceva pentru a compara împotriva.

181
00:08:45,126 --> 00:08:49,140
Și știm că pe partea dreapta
din partea dreapta este sortat.

182
00:08:49,140 --> 00:08:52,770
>> OK, asa ca acum să înghețe din nou și
dau seama unde suntem în poveste.

183
00:08:52,770 --> 00:08:56,120
În matrice de ansamblu,
ceea ce am realizat?

184
00:08:56,120 --> 00:08:58,790
Am realiza de fapt
acum pașii unu și pasul doi.

185
00:08:58,790 --> 00:09:03,300
Am sortat jumătatea stângă, și
am sortat jumătatea din dreapta.

186
00:09:03,300 --> 00:09:08,210
>> Deci, acum, tot ce rămâne este pentru noi
să fuzioneze cele două jumătăți împreună.

187
00:09:08,210 --> 00:09:11,670
Așa că am compara cel mai mic apreciate
Element de fiecare jumătate de matrice

188
00:09:11,670 --> 00:09:13,510
la rândul său, și se procedează.

189
00:09:13,510 --> 00:09:16,535
Una dintre ele este mai mic de trei, așa se duce.

190
00:09:16,535 --> 00:09:19,770
>> Două este mai mică de trei, așa doua trece.

191
00:09:19,770 --> 00:09:22,740
Trei este mai mică de 5, așa de trei merge.

192
00:09:22,740 --> 00:09:25,820
Patru este mai mică de 5, așa cu patru trece.

193
00:09:25,820 --> 00:09:30,210
Apoi cinci este mai mic de șase,
și șase este tot ce rămâne.

194
00:09:30,210 --> 00:09:31,820
>> Acum, știu că a fost o mulțime de pași.

195
00:09:31,820 --> 00:09:33,636
Și am lăsat o mulțime
de memorie în urma noastră.

196
00:09:33,636 --> 00:09:35,260
Și asta e ceea ce aceste pătrate gri sunt.

197
00:09:35,260 --> 00:09:40,540
Și, probabil, m-am simtit ca un, care a avut
mult mai mult decât sortare prin inserție, cu bule

198
00:09:40,540 --> 00:09:42,660
un fel, sau de selecție fel.

199
00:09:42,660 --> 00:09:45,330
>> Dar, de fapt, pentru că o
mulțime de aceste procese

200
00:09:45,330 --> 00:09:48,260
se întâmplă în același time--
care este ceva ce vom, din nou,

201
00:09:48,260 --> 00:09:51,100
vorbesc despre atunci când vorbim despre
recursivitate într-un viitor video--

202
00:09:51,100 --> 00:09:53,799
acest algoritm de fapt
în mod clar este fundamental

203
00:09:53,799 --> 00:09:55,590
diferit de orice
am văzut înainte

204
00:09:55,590 --> 00:09:58,820
dar este, de asemenea, semnificativ
mai eficient.

205
00:09:58,820 --> 00:09:59,532
>> De ce este asta?

206
00:09:59,532 --> 00:10:01,240
Ei bine, în cel mai rău
scenariu, avem

207
00:10:01,240 --> 00:10:04,830
a împărți n elemente sus
și apoi recombina le.

208
00:10:04,830 --> 00:10:06,680
Dar când am recombina
ei, ce facem

209
00:10:06,680 --> 00:10:11,110
este, în principiu dublarea
mărimea matrice mici.

210
00:10:11,110 --> 00:10:14,260
Avem o grămadă de un element
tablouri pe care le în mod eficient

211
00:10:14,260 --> 00:10:16,290
combina în două tablouri de elemente.

212
00:10:16,290 --> 00:10:18,590
Și apoi vom lua cele
două tablouri de elemente

213
00:10:18,590 --> 00:10:21,890
și să le combine împreună în
patru tablouri elemente, și așa mai departe,

214
00:10:21,890 --> 00:10:26,130
și așa mai departe, și așa mai departe, până când vom
au un singur tablou n elemente.

215
00:10:26,130 --> 00:10:29,910
>> Dar cum de multe dublări
nu-l ia pentru a ajunge la n?

216
00:10:29,910 --> 00:10:31,460
Gandeste-te la exemplul cartea de telefon.

217
00:10:31,460 --> 00:10:34,490
De câte ori avem de a rupe
cartea de telefon în jumătate, câte

218
00:10:34,490 --> 00:10:38,370
ori avem de a rupe cartea de telefon
în jumătate, în cazul în care dimensiunea de cartea de telefon

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

220
00:10:39,680 --> 00:10:41,960
Există doar un singur, nu?

221
00:10:41,960 --> 00:10:45,360
>> Deci, există un fel de
Element logaritmică aici.

222
00:10:45,360 --> 00:10:48,590
Dar noi, de asemenea, mai avem cel puțin
uita-te la toate n elemente.

223
00:10:48,590 --> 00:10:53,860
Deci, în cel mai rău caz,
merge sort rulează în n log n.

224
00:10:53,860 --> 00:10:56,160
Trebuie să se uite la
toate n elemente,

225
00:10:56,160 --> 00:11:02,915
și trebuie să le combine
împreună în jurnalul n seturi de trepte.

226
00:11:02,915 --> 00:11:05,290
În cel mai bun caz,
matrice sunt sortate perfect.

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

228
00:11:06,300 --> 00:11:09,980
Dar, pe baza algoritmului avem aici,
mai avem de a împărți și recombina.

229
00:11:09,980 --> 00:11:13,290
Deși în acest caz,
recombinarea este un fel de ineficient.

230
00:11:13,290 --> 00:11:14,720
Nu este necesar.

231
00:11:14,720 --> 00:11:17,580
Dar noi încă trece prin
întregul proces, oricum.

232
00:11:17,580 --> 00:11:21,290
>> Deci, în cel mai bun caz
și în cel mai rău caz,

233
00:11:21,290 --> 00:11:24,970
acest algoritm se execută în n log n timp.

234
00:11:24,970 --> 00:11:29,130
Merge fel este cu siguranta un pic mai complicată
decât celelalte algoritmii principali de sortare

235
00:11:29,130 --> 00:11:33,470
am vorbit despre CS50, dar este
mult mai puternic.

236
00:11:33,470 --> 00:11:35,400
>> Și așa că, dacă găsi vreodată
ocazia să nevoie de ea

237
00:11:35,400 --> 00:11:38,480
sau să-l folosească pentru a sorta o
set mare de date, obtinerea

238
00:11:38,480 --> 00:11:41,940
capul în jurul ideii de recursivitate
va fi foarte puternic.

239
00:11:41,940 --> 00:11:45,270
Și o să vă face
programe într-adevăr mult mai eficient

240
00:11:45,270 --> 00:11:48,700
folosind merge sort fata de orice altceva.

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

242
00:11:49,640 --> 00:11:51,970
Acest lucru este CS50.

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