1
00:00:00,000 --> 00:00:04,419
>> [Гуляе музыка]

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

3
00:00:05,401 --> 00:00:08,460
>> Даг Lloyd: ОК, так што зліццё
роду з'яўляецца яшчэ адным алгарытмам

4
00:00:08,460 --> 00:00:11,200
што мы можам выкарыстоўваць, каб разабрацца
элементы масіва.

5
00:00:11,200 --> 00:00:14,480
Але, як мы ўбачым, ён атрымаў
вельмі прынцыповая розніца

6
00:00:14,480 --> 00:00:17,850
ад выбару гатунку, бурбалка
сартаваць і сартаванне ўстаўкамі

7
00:00:17,850 --> 00:00:20,280
якія робяць яго сапраўды вельмі разумны.

8
00:00:20,280 --> 00:00:24,290
>> Асноўная ідэя зліцця
сартавання для сартавання дробных масіваў

9
00:00:24,290 --> 00:00:27,430
а затым аб'яднаць гэтыя масівы
разам, або аб'яднаць them--

10
00:00:27,430 --> 00:00:31,440
такім чынам name-- ў адсартаваным парадку.

11
00:00:31,440 --> 00:00:34,230
Такім чынам, што сартаванне зліццём робіць
гэта, выкарыстоўваючы інструмент

12
00:00:34,230 --> 00:00:37,290
называецца Рэкурсія, што і
мы будзем казаць аб ў бліжэйшы час,

13
00:00:37,290 --> 00:00:39,720
але мы не казалі пра яшчэ.

14
00:00:39,720 --> 00:00:43,010
>> Вось асноўная ідэя сартавання зліццём.

15
00:00:43,010 --> 00:00:46,320
Сартаваць левую палову масіва,
пры ўмове, N больш 1.

16
00:00:46,320 --> 00:00:49,980
І тое, што я маю на ўвазе, калі кажу,
пры ўмове, N больш, чым 1,

17
00:00:49,980 --> 00:00:53,970
Я думаю, што мы можам пагадзіцца, што, калі масіў
складаецца толькі з аднаго элемента,

18
00:00:53,970 --> 00:00:54,680
гэта сартуецца.

19
00:00:54,680 --> 00:00:56,560
Мы не на самай справе трэба
каб зрабіць што-небудзь з ім.

20
00:00:56,560 --> 00:00:58,059
Мы можам проста аб'явіць яго быць адсартаваныя.

21
00:00:58,059 --> 00:01:00,110
Гэта ўсяго толькі адзін элемент.

22
00:01:00,110 --> 00:01:03,610
>> Так псевдокод, зноў жа,
сартаваць левую палову масіва,

23
00:01:03,610 --> 00:01:08,590
затым адсартаваць правая палова масіў,
а затым аб'яднаць дзве палоўкі разам.

24
00:01:08,590 --> 00:01:11,040
Цяпер, ужо вы маглі б быць
думаючы, што гэта накшталт толькі

25
00:01:11,040 --> 00:01:14,080
Падобна на тое, вы адкладалі the--
Вы на самой справе не робяць нічога.

26
00:01:14,080 --> 00:01:16,330
Вы кажаце адсартаваць левую
палова, сартаваць правую палову,

27
00:01:16,330 --> 00:01:19,335
але ты не кажаш
мне, як ты гэта робіш.

28
00:01:19,335 --> 00:01:22,220
>> Але памятайце, што пакуль
масіў з'яўляецца адзіным элементам,

29
00:01:22,220 --> 00:01:23,705
мы можам аб'явіць яго сартаваць.

30
00:01:23,705 --> 00:01:25,330
Тады мы можам проста абяднаць іх разам.

31
00:01:25,330 --> 00:01:27,788
І гэта на самай справе
Асноўная ідэя ззаду сартавання зліццём,

32
00:01:27,788 --> 00:01:31,150
гэта разбіць яго такім чынам, што
Вашы масівы маюць памер аднаго.

33
00:01:31,150 --> 00:01:33,430
І тады вы аднавіць адтуль.

34
00:01:33,430 --> 00:01:35,910
>> Зліццё роду, безумоўна,
складаны алгарытм.

35
00:01:35,910 --> 00:01:38,210
І гэта таксама трохі
складаней візуалізаваць.

36
00:01:38,210 --> 00:01:41,870
Так, мы спадзяемся, візуалізацыя, што я
ёсць тут, дапаможа Вам прытрымлівацца ўздоўж.

37
00:01:41,870 --> 00:01:45,640
І я буду старацца з усіх сіл, каб распавесці рэчы
і прайсці праз гэта крыху больш,

38
00:01:45,640 --> 00:01:49,180
павольней, чым астатніх
проста мы спадзяемся атрымаць вашу галаву

39
00:01:49,180 --> 00:01:51,800
вакол ідэй, якія ляжаць сартавання зліццём.

40
00:01:51,800 --> 00:01:54,680
>> Такім чынам, мы маем той жа масіў у якасці
іншыя алгарытм сартавання відэа

41
00:01:54,680 --> 00:01:57,120
калі вы бачылі them--
Масіў шэсць элемент.

42
00:01:57,120 --> 00:02:02,110
І наша псевдокод тут код з'яўляецца свайго роду
левая палова, сартаваць правую палову,

43
00:02:02,110 --> 00:02:03,890
аб'яднаць дзве палоўкі разам.

44
00:02:03,890 --> 00:02:09,770
Такім чынам, давайце гэта вельмі цёмна чырвоны цэгла
масіва і адсартаваць левую палову.

45
00:02:09,770 --> 00:02:13,380
>> Так на дадзены момант, мы збіраемся
ігнараваць рэчы справа.

46
00:02:13,380 --> 00:02:15,740
Гэта там, але мы
ня на гэтым кроку яшчэ.

47
00:02:15,740 --> 00:02:18,220
Мы не Сартаванне
Правая палова масіва.

48
00:02:18,220 --> 00:02:21,037
Мы ў той левага
палова масіва.

49
00:02:21,037 --> 00:02:22,870
І толькі дзеля
быць трохі больш

50
00:02:22,870 --> 00:02:26,480
ясна, так што я магу звярнуцца
на тое, што крок мы на,

51
00:02:26,480 --> 00:02:29,800
Я збіраюся пераключыць
Колер гэтага набору апельсіна.

52
00:02:29,800 --> 00:02:33,190
Зараз, мы ўсё яшчэ гаворым пра
ж левая палова зыходнага масіва.

53
00:02:33,190 --> 00:02:38,520
Але я спадзяюся, што, будучы ў стане
см колеру розных прадметаў,

54
00:02:38,520 --> 00:02:40,900
гэта зробіць яго крыху больш
ясна, што тут адбываецца.

55
00:02:40,900 --> 00:02:43,270
>> ОК, так што цяпер у нас ёсць
тры элемента масіва.

56
00:02:43,270 --> 00:02:46,420
Як мы сартуем левую палову гэтага
Масіў, які да гэтага часу гэты крок?

57
00:02:46,420 --> 00:02:49,400
Мы спрабуем, каб адсартаваць левую
палова з чырвонай цэглы array--

58
00:02:49,400 --> 00:02:52,410
левая палова якога
Я цяпер афарбаваны ў аранжавы колер.

59
00:02:52,410 --> 00:02:54,840
>> Ну, мы маглі б паспрабаваць
паўтарыць гэты працэс зноў.

60
00:02:54,840 --> 00:02:56,756
Такім чынам, мы ўсё яшчэ ў
Сярэдзіна спрабуючы разабрацца

61
00:02:56,756 --> 00:02:58,700
левая палова поўнай масіва.

62
00:02:58,700 --> 00:03:00,450
Левая палова
Масіў, я толькі збіраюся

63
00:03:00,450 --> 00:03:03,910
адвольна вырашаць, што левая палова
будзе менш, чым у правай палове,

64
00:03:03,910 --> 00:03:06,550
таму што гэта адбываецца з
складаецца з трох элементаў.

65
00:03:06,550 --> 00:03:11,260
>> І таму я хачу сказаць, што
левая палова левай палове масіва

66
00:03:11,260 --> 00:03:14,050
гэта проста элемент пяць.

67
00:03:14,050 --> 00:03:18,360
Пяць, ён быў адзін элемент
Масіў, мы ведаем, як разбірацца.

68
00:03:18,360 --> 00:03:21,615
І так пяць сартуецца.

69
00:03:21,615 --> 00:03:22,990
Мы проста заявіць, што.

70
00:03:22,990 --> 00:03:24,890
Гэта адзін элемент масіва.

71
00:03:24,890 --> 00:03:29,015
>> Такім чынам, мы ў цяперашні час сартуюцца
левая палова левай half--

72
00:03:29,015 --> 00:03:33,190
дакладней, мы адсартаваныя
левая палова памяранца.

73
00:03:33,190 --> 00:03:37,970
Так што цяпер, для таго, каб па-ранейшаму поўная
левая палова агульнага масіва,

74
00:03:37,970 --> 00:03:43,481
мы павінны разабрацца ў правую палову
апельсіна, або гэты матэрыял.

75
00:03:43,481 --> 00:03:44,230
Як мы гэта робім?

76
00:03:44,230 --> 00:03:45,930
Ну, у нас ёсць масіў з двух элементаў.

77
00:03:45,930 --> 00:03:50,470
Такім чынам, мы можам адсартаваць левую палову
масіва, які два.

78
00:03:50,470 --> 00:03:52,090
Два гэта адзіны элемент.

79
00:03:52,090 --> 00:03:55,890
Так што гэта сартуецца па змаўчанні.
Тады мы можам адсартаваць правую палову

80
00:03:55,890 --> 00:03:58,530
той частцы масіва, адзін.

81
00:03:58,530 --> 00:04:00,210
Гэта свайго роду па змаўчанні.

82
00:04:00,210 --> 00:04:03,610
>> Зараз гэта ў першы раз
мы дасягнулі крок зліцця.

83
00:04:03,610 --> 00:04:06,135
Мы завяршылі, хоць
мы зараз выгляд ўкладзеных down--

84
00:04:06,135 --> 00:04:08,420
і гэта свайго роду хітры
што з рэкурсіі,

85
00:04:08,420 --> 00:04:10,930
Вы павінны трымаць
галаву пра тое, дзе мы знаходзімся.

86
00:04:10,930 --> 00:04:15,560
Такім чынам, мы свайго роду злева
палова аранжавага часткі.

87
00:04:15,560 --> 00:04:21,280
>> І зараз, мы знаходзімся ў сярэдзіне сартавання
правая палова аранжавага часткі.

88
00:04:21,280 --> 00:04:25,320
І ў гэтым працэсе, мы
цяпер збіраецца быць на крок,

89
00:04:25,320 --> 00:04:27,850
аб'яднаць дзве палоўкі разам.

90
00:04:27,850 --> 00:04:31,700
Калі мы глядзім на дзве паловы
масіва, мы бачым два і адзін.

91
00:04:31,700 --> 00:04:33,880
Які элемент менш?

92
00:04:33,880 --> 00:04:35,160
Адзін.

93
00:04:35,160 --> 00:04:36,760
>> Тады, які элемент менш?

94
00:04:36,760 --> 00:04:38,300
Ну, гэта два ці нічога.

95
00:04:38,300 --> 00:04:39,910
Так што гэта два.

96
00:04:39,910 --> 00:04:43,690
Так што цяпер, проста зноў кадр
дзе мы знаходзімся ў кантэксце

97
00:04:43,690 --> 00:04:48,230
мы сартуюцца
левая палова апельсіна

98
00:04:48,230 --> 00:04:49,886
а правая палова паходжання.

99
00:04:49,886 --> 00:04:52,510
Я ведаю, што я змяніў колеру
зноў, але гэта, дзе мы былі.

100
00:04:52,510 --> 00:04:54,676
І прычына Я зрабіў гэта
у тым, што гэты працэс

101
00:04:54,676 --> 00:04:57,870
працягваць ісці, паўтараючы ўніз.

102
00:04:57,870 --> 00:05:00,500
Мы адсартаваныя левы
палова былога аранжавага

103
00:05:00,500 --> 00:05:02,590
а правая палова ранейшага аранжавага колеру.

104
00:05:02,590 --> 00:05:05,620
>> Цяпер нам трэба аб'яднаць тых,
дзве палоўкі разам таксама.

105
00:05:05,620 --> 00:05:07,730
Гэта крок, які мы зараз знаходзіцеся.

106
00:05:07,730 --> 00:05:11,440
Такім чынам, мы разгледзім усе з
элементы, якія ў цяперашні час з'яўляюцца зялёны,

107
00:05:11,440 --> 00:05:12,972
левая палова зыходнага масіва.

108
00:05:12,972 --> 00:05:14,680
І мы аб'яднаем тых,
выкарыстоўваючы той жа самы працэс

109
00:05:14,680 --> 00:05:18,660
мы зрабілі для аб'яднання дзвюх
і адзін толькі момант таму.

110
00:05:18,660 --> 00:05:23,080
>> Левая палова, найменшы
элемент на левай палове пяць.

111
00:05:23,080 --> 00:05:25,620
Найменшую элемент на
правая палова з'яўляецца адным.

112
00:05:25,620 --> 00:05:27,370
Які з іх з'яўляецца менш?

113
00:05:27,370 --> 00:05:29,260
Адзін.

114
00:05:29,260 --> 00:05:32,250
>> Найменшую элемент на
левая палова пяць.

115
00:05:32,250 --> 00:05:35,540
Найменшую элемент на
правая палова гэта два.

116
00:05:35,540 --> 00:05:36,970
Што найменшую?

117
00:05:36,970 --> 00:05:38,160
Два.

118
00:05:38,160 --> 00:05:41,540
І тады, нарэшце, пяць
нічога, мы можам сказаць, пяць.

119
00:05:41,540 --> 00:05:43,935
>> Такім чынам, карціна, давайце
перапынак на секунду

120
00:05:43,935 --> 00:05:46,080
і высветліць, дзе мы знаходзімся.

121
00:05:46,080 --> 00:05:48,580
Калі б мы пачалі з
у самым пачатку, мы

122
00:05:48,580 --> 00:05:51,640
Цяпер завершаны
агульная масіў толькі

123
00:05:51,640 --> 00:05:53,810
адзін крок кода псевдокода тут.

124
00:05:53,810 --> 00:05:56,645
Мы сартуюцца
левая палова масіва.

125
00:05:56,645 --> 00:05:59,490
>> Нагадаем, што арыгінальны
Загад быў пяць, два, адзін.

126
00:05:59,490 --> 00:06:02,570
Ідучы праз гэты працэс
і гнездавання ўніз і паўтараць,

127
00:06:02,570 --> 00:06:05,990
працягваючы парушаць праблему
на больш дробныя і больш дробныя часткі,

128
00:06:05,990 --> 00:06:09,670
мы ўжо завяршылі
крок адзін з псевдокода

129
00:06:09,670 --> 00:06:13,940
на працягу ўсяго пачатковай масіва.

130
00:06:13,940 --> 00:06:16,670
Мы разабраліся левую палову.

131
00:06:16,670 --> 00:06:18,670
>> Так што цяпер давайце замарозіць там.

132
00:06:18,670 --> 00:06:23,087
А цяпер давайце разбярэмся права
палова зыходнага масіва.

133
00:06:23,087 --> 00:06:25,670
І мы збіраемся зрабіць гэта,
перажывае тое ж самае итеративный

134
00:06:25,670 --> 00:06:30,630
працэс разбурэння рэчы ўніз
, А затым аб'ядноўваць іх разам.

135
00:06:30,630 --> 00:06:34,290
>> Такім чынам, левая палова з
чырвоны ці левая палова

136
00:06:34,290 --> 00:06:38,830
правай паловы першапачатковага
Масіў, я збіраюся сказаць, тры.

137
00:06:38,830 --> 00:06:40,312
Зноў жа, я тут быць паслядоўным.

138
00:06:40,312 --> 00:06:42,020
Калі ў вас ёсць няцотная
Колькасць элементаў, яго

139
00:06:42,020 --> 00:06:44,478
на самай справе не мае значэння,
Вы робіце левая менш

140
00:06:44,478 --> 00:06:45,620
або права паменш.

141
00:06:45,620 --> 00:06:49,230
>> Важна тое, што кожны раз, калі вам
сутыкнуліся з гэтай праблемай у правядзенні

142
00:06:49,230 --> 00:06:51,422
зліццё, вам трэба быць паслядоўным.

143
00:06:51,422 --> 00:06:53,505
Вы альбо павінны заўсёды
зрабіць левы бок менш

144
00:06:53,505 --> 00:06:55,421
ці заўсёды трэба зрабіць
правая бок менш.

145
00:06:55,421 --> 00:06:57,720
Тут я выбраў, каб заўсёды
зрабіць левы бок менш

146
00:06:57,720 --> 00:07:04,380
калі мой масіў, ці мой
суб-масіва, з'яўляецца няцотным памеру.

147
00:07:04,380 --> 00:07:07,420
>> Тры ёсць адзін элемент,
і таму ён адсартаваны.

148
00:07:07,420 --> 00:07:10,860
Мы выкарыстала гэта здагадка
на працягу ўсёй нашай працэсе да гэтага часу.

149
00:07:10,860 --> 00:07:15,020
Так што цяпер давайце разбярэмся права
палова правай палове,

150
00:07:15,020 --> 00:07:18,210
ці правая палова чырвонага.

151
00:07:18,210 --> 00:07:20,390
>> Зноў жа, мы павінны падзяліць гэта ўніз.

152
00:07:20,390 --> 00:07:21,910
Гэта не адзіны элемент масіва.

153
00:07:21,910 --> 00:07:23,970
Мы не можам аб'явіць яго сартаваць.

154
00:07:23,970 --> 00:07:27,060
І так па-першае, мы збіраемся
сартаваць левую палову.

155
00:07:27,060 --> 00:07:31,620
>> Левая палова адзін элемент,
так што гэта свайго роду па змаўчанні.

156
00:07:31,620 --> 00:07:34,840
Тады мы ідзем, каб адсартаваць права
палова, што адзін элемент.

157
00:07:34,840 --> 00:07:41,250
Гэта сартуюцца па змаўчанні. І зараз,
мы можам аб'яднаць гэтыя два разам.

158
00:07:41,250 --> 00:07:45,820
Чатыры менш, і
затым шэсць менш.

159
00:07:45,820 --> 00:07:48,870
>> Зноў жа, тое, што мы зрабілі ў гэты момант?

160
00:07:48,870 --> 00:07:52,512
Мы адсартаваныя левы
палова правай палове.

161
00:07:52,512 --> 00:07:54,720
Або вярнуцца да арыгіналу
колеру, якія былі там,

162
00:07:54,720 --> 00:07:57,875
мы адсартаваныя левы
палова мяккага чырвонага.

163
00:07:57,875 --> 00:08:00,416
Першапачаткова ён быў цёмна-цэгла
чырвоны і цяпер гэта мякчэй чырвоны,

164
00:08:00,416 --> 00:08:02,350
ці гэта была мякчэй чырвоны.

165
00:08:02,350 --> 00:08:05,145
>> А потым мы сартуюцца
Правая палова мяккага чырвонага.

166
00:08:05,145 --> 00:08:08,270
Цяпер, добра, яны зялёныя зноў, толькі
таму што мы збіраемся праз працэс.

167
00:08:08,270 --> 00:08:10,720
І мы павінны паўтарыць
гэта зноў і зноў.

168
00:08:10,720 --> 00:08:14,695
>> Так што цяпер мы можам аб'яднаць тых,
дзве палоўкі разам.

169
00:08:14,695 --> 00:08:15,820
І гэта тое, што мы робім тут.

170
00:08:15,820 --> 00:08:17,653
Так чорнай лініі толькі
падзяліць левую палову

171
00:08:17,653 --> 00:08:19,690
а правая палова гэтага роду часткі.

172
00:08:19,690 --> 00:08:24,310
>> Мы параўноўваем найменшае значэнне
на левай баку array--

173
00:08:24,310 --> 00:08:26,710
або, прабачце, найменшая
Значэнне левай палове

174
00:08:26,710 --> 00:08:30,790
найменшаму значэнні правы
палова і выявілі, што тры менш.

175
00:08:30,790 --> 00:08:32,530
А цяпер крыху аптымізацыі, праўда?

176
00:08:32,530 --> 00:08:35,175
Там насамрэч нічога
пакінулі на левай баку.

177
00:08:35,175 --> 00:08:37,440
>> Там няма нічога астатнія
на левай баку,

178
00:08:37,440 --> 00:08:40,877
таму мы можам эфектыўна
проста move-- мы можам аб'явіць

179
00:08:40,877 --> 00:08:42,960
астатняе на самай справе
сартуюцца і толькі лавіраваць яго

180
00:08:42,960 --> 00:08:45,126
на, таму што няма нічога
яшчэ для параўнання.

181
00:08:45,126 --> 00:08:49,140
І мы ведаем, што правы бок
з правага боку сартуецца.

182
00:08:49,140 --> 00:08:52,770
>> ОК, так што цяпер давайце зноў і замарозіць
высветліць, дзе мы знаходзімся ў гісторыі.

183
00:08:52,770 --> 00:08:56,120
У агульным масіве,
Што мы зрабілі?

184
00:08:56,120 --> 00:08:58,790
Мы на самай справе выканаць
Цяпер крокі адно і другі этап.

185
00:08:58,790 --> 00:09:03,300
Мы адсартаваныя левую палову, і
мы адсартаваныя правую палову.

186
00:09:03,300 --> 00:09:08,210
>> Так што цяпер, усё, што застаецца для нас
аб'яднаць гэтыя дзве палоўкі разам.

187
00:09:08,210 --> 00:09:11,670
Такім чынам, мы параўноўваем самы нізкі цэніцца
элемент кожнай палове масіва

188
00:09:11,670 --> 00:09:13,510
у сваю чаргу, і працягнуць.

189
00:09:13,510 --> 00:09:16,535
Адным з іх з'яўляецца менш чым тры, так што ідзе.

190
00:09:16,535 --> 00:09:19,770
>> Два менш трох, так што два ідзе.

191
00:09:19,770 --> 00:09:22,740
Тры менш чым 5, так тры ідзе.

192
00:09:22,740 --> 00:09:25,820
Чатыры менш, чым 5, так чацвёрка заходзіць.

193
00:09:25,820 --> 00:09:30,210
Тады пяць менш, чым шэсць,
і шэсць гэта ўсё, што застаецца.

194
00:09:30,210 --> 00:09:31,820
>> Зараз, я ведаю, што было шмат крокаў.

195
00:09:31,820 --> 00:09:33,636
І мы пакінулі шмат
памяці ў нашай хвалі.

196
00:09:33,636 --> 00:09:35,260
І гэта тое, што гэтыя шэрыя квадраты.

197
00:09:35,260 --> 00:09:40,540
І гэта, верагодна, адчуваў, што гэта ўзяў
значна даўжэй, чым ўстаўкі роду, бурбалка

198
00:09:40,540 --> 00:09:42,660
сартаваць, ці выбар роду.

199
00:09:42,660 --> 00:09:45,330
>> Але на самой справе, таму што
Многія з гэтых працэсаў

200
00:09:45,330 --> 00:09:48,260
адбываюцца ў той жа time--
што тое, што мы будзем, зноў жа,

201
00:09:48,260 --> 00:09:51,100
казаць, калі мы гаворым пра
Рэкурсія ў будучыні video--

202
00:09:51,100 --> 00:09:53,799
гэты алгарытм на самай справе
ясна прынцыпова

203
00:09:53,799 --> 00:09:55,590
адрозніваецца ад усяго,
мы бачылі раней

204
00:09:55,590 --> 00:09:58,820
але таксама значна
больш эфектыўным.

205
00:09:58,820 --> 00:09:59,532
>> Чаму так?

206
00:09:59,532 --> 00:10:01,240
Ну, у горшым
сцэнар, у нас ёсць

207
00:10:01,240 --> 00:10:04,830
падзяліць п элементаў да
а затым зліваюць.

208
00:10:04,830 --> 00:10:06,680
Але калі мы аб'яднаць
ім, што мы робім

209
00:10:06,680 --> 00:10:11,110
у асноўным падваенне
Памер меншых масіваў.

210
00:10:11,110 --> 00:10:14,260
У нас ёсць куча аднаго элемента
масівы, якія мы эфектыўна

211
00:10:14,260 --> 00:10:16,290
аб'яднаць у двух масівах элементаў.

212
00:10:16,290 --> 00:10:18,590
А потым мы возьмем тых,
два масіва элемент

213
00:10:18,590 --> 00:10:21,890
і аб'яднаць іх разам у
чатыры масіва элементаў, і гэтак далей,

214
00:10:21,890 --> 00:10:26,130
ня і гэтак далей, і гэтак далей, да таго часу,
ёсць адзін масіў п элементаў.

215
00:10:26,130 --> 00:10:29,910
>> Але колькі падваення
гэта, каб дабрацца да п?

216
00:10:29,910 --> 00:10:31,460
Ўспомніце, напрыклад тэлефоннай кнігі.

217
00:10:31,460 --> 00:10:34,490
Колькі разоў мы павінны ірваць
тэлефонная кніга на палову, колькі яшчэ

218
00:10:34,490 --> 00:10:38,370
раз мы павінны ірваць тэлефонную кнігу
напалову, калі памер тэлефоннай кнігі

219
00:10:38,370 --> 00:10:39,680
у два разы?

220
00:10:39,680 --> 00:10:41,960
Там толькі адзін, праўда?

221
00:10:41,960 --> 00:10:45,360
>> Так што нейкая
лагарыфмічная элементам тут.

222
00:10:45,360 --> 00:10:48,590
Але мы таксама ўсё яшчэ ёсць, па меншай меры
глядзець на ўсе п элементаў.

223
00:10:48,590 --> 00:10:53,860
Такім чынам, у горшым выпадку,
сартаванне зліццём працуе ў п часопіса п.

224
00:10:53,860 --> 00:10:56,160
Мы павінны глядзець на
усе п элементаў,

225
00:10:56,160 --> 00:11:02,915
і мы павінны аб'яднаць іх
разам у часопісе н набораў крокаў.

226
00:11:02,915 --> 00:11:05,290
У лепшым выпадку,
масіў выдатна адсартаваныя.

227
00:11:05,290 --> 00:11:06,300
Гэта выдатна.

228
00:11:06,300 --> 00:11:09,980
Але на аснове алгарытму мы маем тут,
мы ўсё яшчэ павінны падзяліць, а затым.

229
00:11:09,980 --> 00:11:13,290
Хоць у гэтым выпадку
рекомбинирующий накшталт неэфектыўнымі.

230
00:11:13,290 --> 00:11:14,720
Яна не патрэбна.

231
00:11:14,720 --> 00:11:17,580
Але мы па-ранейшаму ісці праз
увесь працэс у любым выпадку.

232
00:11:17,580 --> 00:11:21,290
>> Такім чынам, у лепшым выпадку
а ў горшым выпадку,

233
00:11:21,290 --> 00:11:24,970
гэты алгарытм працуе ў часопісе н н часу.

234
00:11:24,970 --> 00:11:29,130
Зліццё роду, безумоўна, крыху больш складана
чым іншых асноўных алгарытмаў сартавання

235
00:11:29,130 --> 00:11:33,470
мы гаварылі пра CS50, але
істотна больш магутным.

236
00:11:33,470 --> 00:11:35,400
>> І таму, калі вы калі-небудзь знайсці
Нагодай для гэта трэба

237
00:11:35,400 --> 00:11:38,480
або выкарыстоўваць яго для сартавання
вялікі набор дадзеных, атрыманне

238
00:11:38,480 --> 00:11:41,940
Ваша галава вакол ідэі рэкурсіі
будзе вельмі магутны.

239
00:11:41,940 --> 00:11:45,270
І гэта будзе зрабіць свой
праграмы сапраўды нашмат больш эфектыўна

240
00:11:45,270 --> 00:11:48,700
з дапамогай сартаванне зліццём супраць што-небудзь яшчэ.

241
00:11:48,700 --> 00:11:49,640
Я Дуг Лойд.

242
00:11:49,640 --> 00:11:51,970
Гэта CS50.

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