1
00:00:00,000 --> 00:00:04,419
>> [MUSIC CHƠI]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, do đó, một hợp nhất
sort là thuật toán nào khác

4
00:00:08,460 --> 00:00:11,200
rằng chúng ta có thể sử dụng để sắp xếp ra
các yếu tố của một mảng.

5
00:00:11,200 --> 00:00:14,480
Tuy nhiên, như chúng ta sẽ thấy, nó có một
sự khác biệt rất cơ bản

6
00:00:14,480 --> 00:00:17,850
từ sắp xếp chọn, bong bóng
sắp xếp, và sắp xếp chèn

7
00:00:17,850 --> 00:00:20,280
mà làm cho nó thực sự rất thông minh.

8
00:00:20,280 --> 00:00:24,290
>> Ý tưởng cơ bản đằng sau hợp nhất
sort để sắp xếp mảng nhỏ hơn

9
00:00:24,290 --> 00:00:27,430
và sau đó kết hợp những mảng
với nhau, hoặc hợp nhất them--

10
00:00:27,430 --> 00:00:31,440
do đó name-- trong thứ tự sắp xếp.

11
00:00:31,440 --> 00:00:34,230
Cách mà hợp nhất phân loại hiện
đây là bằng cách tận dụng một công cụ

12
00:00:34,230 --> 00:00:37,290
được gọi là đệ quy, đó là những gì
chúng ta sẽ nói về sớm,

13
00:00:37,290 --> 00:00:39,720
nhưng chúng tôi đã không thực sự nói về chưa.

14
00:00:39,720 --> 00:00:43,010
>> Dưới đây là những ý tưởng cơ bản đằng sau sắp xếp hợp nhất.

15
00:00:43,010 --> 00:00:46,320
Sắp xếp một nửa trái của mảng,
giả sử n là lớn hơn 1.

16
00:00:46,320 --> 00:00:49,980
Và những gì tôi có nghĩa là khi tôi nói
giả sử n là lớn hơn 1 là,

17
00:00:49,980 --> 00:00:53,970
Tôi nghĩ rằng chúng ta có thể đồng ý rằng nếu một mảng
chỉ bao gồm một yếu tố duy nhất,

18
00:00:53,970 --> 00:00:54,680
nó được sắp xếp.

19
00:00:54,680 --> 00:00:56,560
Chúng tôi không thực sự cần
để làm bất cứ điều gì với nó.

20
00:00:56,560 --> 00:00:58,059
Chúng tôi chỉ có thể khai báo nó sẽ được sắp xếp.

21
00:00:58,059 --> 00:01:00,110
Nó chỉ là một yếu tố duy nhất.

22
00:01:00,110 --> 00:01:03,610
>> Vì vậy, các mã giả, một lần nữa, là
sắp xếp các nửa trái của mảng,

23
00:01:03,610 --> 00:01:08,590
sau đó sắp xếp đúng một nửa mảng,
sau đó hợp nhất hai nửa lại với nhau.

24
00:01:08,590 --> 00:01:11,040
Bây giờ, đã có thể là bạn
suy nghĩ, nó loại chỉ

25
00:01:11,040 --> 00:01:14,080
Nghe có vẻ như bạn đang đặt ra the--
bạn không thực sự làm bất cứ điều gì.

26
00:01:14,080 --> 00:01:16,330
Bạn đang nói sắp xếp bên trái
một nửa, sắp xếp một nửa bên phải,

27
00:01:16,330 --> 00:01:19,335
nhưng bạn không nói
tôi làm thế nào bạn đang làm nó.

28
00:01:19,335 --> 00:01:22,220
>> Nhưng hãy nhớ rằng miễn là
một mảng là một yếu tố duy nhất,

29
00:01:22,220 --> 00:01:23,705
chúng ta có thể khai báo nó được sắp xếp.

30
00:01:23,705 --> 00:01:25,330
Sau đó, chúng tôi chỉ có thể kết hợp chúng lại với nhau.

31
00:01:25,330 --> 00:01:27,788
Và đó thực sự là
Ý tưởng cơ bản đằng sau sắp xếp hợp nhất,

32
00:01:27,788 --> 00:01:31,150
là để phá vỡ nó xuống để
mảng của bạn có kích thước một.

33
00:01:31,150 --> 00:01:33,430
Và sau đó bạn xây dựng lại từ đó.

34
00:01:33,430 --> 00:01:35,910
>> Hợp nhất phân loại là chắc chắn
một thuật toán phức tạp.

35
00:01:35,910 --> 00:01:38,210
Và nó cũng là một chút
phức tạp để hình dung.

36
00:01:38,210 --> 00:01:41,870
Vì vậy, hy vọng, sự hình dung rằng tôi
có ở đây sẽ giúp bạn theo cùng.

37
00:01:41,870 --> 00:01:45,640
Và tôi sẽ cố gắng hết sức mình để tường thuật những điều
và tiến hành thông qua nhiều hơn một chút

38
00:01:45,640 --> 00:01:49,180
chậm hơn so với những người khác
chỉ để hy vọng có được đầu của bạn

39
00:01:49,180 --> 00:01:51,800
xung quanh ý tưởng đằng sau sắp xếp hợp nhất.

40
00:01:51,800 --> 00:01:54,680
>> Vì vậy, chúng tôi có cùng một mảng như
phân loại video thuật toán khác

41
00:01:54,680 --> 00:01:57,120
nếu bạn đã nhìn thấy them--
một mảng sáu yếu tố.

42
00:01:57,120 --> 00:02:02,110
Và mã giả của chúng tôi ở đây là loại
nửa bên trái, sắp xếp một nửa bên phải,

43
00:02:02,110 --> 00:02:03,890
hợp nhất hai nửa lại với nhau.

44
00:02:03,890 --> 00:02:09,770
Vì vậy, chúng ta hãy gạch đỏ này rất tối
mảng và sắp xếp các nửa trái của nó.

45
00:02:09,770 --> 00:02:13,380
>> Vì vậy, trong thời gian này, chúng ta sẽ
để bỏ qua các công cụ bên phải.

46
00:02:13,380 --> 00:02:15,740
Nó ở đó, nhưng chúng tôi
không phải ở đó bước nào.

47
00:02:15,740 --> 00:02:18,220
Chúng tôi không phải lúc sắp xếp các
nửa bên phải của mảng.

48
00:02:18,220 --> 00:02:21,037
Chúng tôi đang ở loại trái
một nửa của mảng.

49
00:02:21,037 --> 00:02:22,870
Và chỉ vì lợi ích
của việc nhiều hơn một chút

50
00:02:22,870 --> 00:02:26,480
rõ ràng, vì vậy tôi có thể tham khảo
với những gì chúng tôi bước vào,

51
00:02:26,480 --> 00:02:29,800
Tôi sẽ chuyển đổi
Màu sắc của bộ này để màu da cam.

52
00:02:29,800 --> 00:02:33,190
Bây giờ, chúng tôi vẫn nói về các
cùng một nửa bên trái của mảng ban đầu.

53
00:02:33,190 --> 00:02:38,520
Nhưng tôi hy vọng rằng bằng việc có thể
tham khảo các màu sắc của các mặt hàng khác nhau,

54
00:02:38,520 --> 00:02:40,900
nó sẽ làm cho nó nhiều hơn một chút
rõ ràng những gì đang xảy ra ở đây.

55
00:02:40,900 --> 00:02:43,270
>> OK, vì vậy bây giờ chúng ta có một
ba phần tử mảng.

56
00:02:43,270 --> 00:02:46,420
Làm thế nào để chúng tôi sắp xếp nửa trái này
mảng, mà vẫn là bước này?

57
00:02:46,420 --> 00:02:49,400
Chúng tôi đang cố gắng để sắp xếp bên trái
một nửa của gạch array-- đỏ

58
00:02:49,400 --> 00:02:52,410
nửa bên trái đó
Bây giờ tôi đã có màu cam.

59
00:02:52,410 --> 00:02:54,840
>> Vâng, chúng ta có thể thử và
lặp lại quá trình này một lần nữa.

60
00:02:54,840 --> 00:02:56,756
Vì vậy, chúng tôi vẫn đang trong
giữa cố gắng sắp xếp

61
00:02:56,756 --> 00:02:58,700
nửa bên trái của mảng đầy đủ.

62
00:02:58,700 --> 00:03:00,450
Nửa bên trái của
mảng, tôi chỉ cần đi

63
00:03:00,450 --> 00:03:03,910
tự ý quyết định rằng nửa trái
sẽ nhỏ hơn so với nửa bên phải,

64
00:03:03,910 --> 00:03:06,550
bởi vì điều này sẽ xảy ra
bao gồm ba yếu tố.

65
00:03:06,550 --> 00:03:11,260
>> Và do đó, tôi sẽ nói rằng
nửa bên trái của một nửa trái mảng

66
00:03:11,260 --> 00:03:14,050
chỉ là những yếu tố năm.

67
00:03:14,050 --> 00:03:18,360
Năm, là một yếu tố duy nhất
mảng, chúng tôi biết làm thế nào để sắp xếp nó.

68
00:03:18,360 --> 00:03:21,615
Và như vậy năm được sắp xếp.

69
00:03:21,615 --> 00:03:22,990
Chúng tôi chỉ muốn khai báo đó.

70
00:03:22,990 --> 00:03:24,890
Đó là một mảng yếu tố duy nhất.

71
00:03:24,890 --> 00:03:29,015
>> Vì vậy, bây giờ chúng tôi đã sắp xếp các
nửa bên trái của half-- trái

72
00:03:29,015 --> 00:03:33,190
hay đúng hơn, chúng tôi đã sắp xếp các
nửa bên trái của màu da cam.

73
00:03:33,190 --> 00:03:37,970
Vì vậy, bây giờ, để vẫn có đầy đủ
nửa bên trái của mảng tổng thể,

74
00:03:37,970 --> 00:03:43,481
chúng ta cần phải sắp xếp một nửa bên phải
của màu da cam, hoặc các công cụ này.

75
00:03:43,481 --> 00:03:44,230
Làm thế nào để chúng tôi làm điều đó?

76
00:03:44,230 --> 00:03:45,930
Vâng, chúng tôi có một mảng hai yếu tố.

77
00:03:45,930 --> 00:03:50,470
Vì vậy, chúng tôi có thể sắp xếp một nửa còn lại
của các mảng, mà là hai.

78
00:03:50,470 --> 00:03:52,090
Hai là một yếu tố duy nhất.

79
00:03:52,090 --> 00:03:55,890
Vì vậy, nó được sắp xếp theo mặc định.
Sau đó chúng tôi có thể sắp xếp một nửa bên phải

80
00:03:55,890 --> 00:03:58,530
phần đó của một dãy, một sự.

81
00:03:58,530 --> 00:04:00,210
Đó là loại mặc định.

82
00:04:00,210 --> 00:04:03,610
>> Điều này bây giờ là lần đầu tiên
chúng tôi đã đạt đến một bước sáp nhập.

83
00:04:03,610 --> 00:04:06,135
Chúng tôi đã hoàn thành, mặc dù
chúng tôi hiện loại lồng down--

84
00:04:06,135 --> 00:04:08,420
và đó là sắp xếp của các khó khăn
điều với đệ quy là,

85
00:04:08,420 --> 00:04:10,930
bạn cần để giữ cho bạn
đi về nơi mà chúng ta đang có.

86
00:04:10,930 --> 00:04:15,560
Vì vậy, chúng tôi đã loại trái
một nửa của phần cam.

87
00:04:15,560 --> 00:04:21,280
>> Và bây giờ, chúng ta đang ở giữa các phân loại
nửa bên phải của phần cam.

88
00:04:21,280 --> 00:04:25,320
Và trong quá trình đó, chúng ta
bây giờ về để được ở bước,

89
00:04:25,320 --> 00:04:27,850
hợp nhất hai nửa lại với nhau.

90
00:04:27,850 --> 00:04:31,700
Khi chúng ta nhìn vào hai nửa
của mảng, chúng ta thấy hai và một.

91
00:04:31,700 --> 00:04:33,880
Yếu tố nào là nhỏ?

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

93
00:04:35,160 --> 00:04:36,760
>> Sau đó, yếu tố nào là nhỏ?

94
00:04:36,760 --> 00:04:38,300
Vâng, đó là hai hoặc không có gì.

95
00:04:38,300 --> 00:04:39,910
Vì vậy, nó là hai.

96
00:04:39,910 --> 00:04:43,690
Vì vậy, bây giờ, chỉ để lại khung
nơi chúng tôi đang trong bối cảnh,

97
00:04:43,690 --> 00:04:48,230
chúng tôi đã sắp xếp các
nửa bên trái của màu da cam

98
00:04:48,230 --> 00:04:49,886
và nửa bên phải của nguồn gốc.

99
00:04:49,886 --> 00:04:52,510
Tôi biết tôi đã thay đổi màu sắc
một lần nữa, nhưng đó là nơi chúng tôi.

100
00:04:52,510 --> 00:04:54,676
Và lý do tôi đã làm điều này
là bởi vì quá trình này là

101
00:04:54,676 --> 00:04:57,870
sẽ tiếp tục đi, lặp lại.

102
00:04:57,870 --> 00:05:00,500
Chúng tôi đã sắp xếp bên trái
một nửa của màu da cam cũ

103
00:05:00,500 --> 00:05:02,590
và nửa bên phải của màu da cam cũ.

104
00:05:02,590 --> 00:05:05,620
>> Bây giờ, chúng ta cần phải hợp nhất những
hai nửa lại với nhau quá.

105
00:05:05,620 --> 00:05:07,730
Đó là bước chúng ta đang ở trên.

106
00:05:07,730 --> 00:05:11,440
Vì vậy, chúng ta xem xét tất cả các
yếu tố mà bây giờ là màu xanh lá cây,

107
00:05:11,440 --> 00:05:12,972
nửa bên trái của mảng ban đầu.

108
00:05:12,972 --> 00:05:14,680
Và chúng tôi kết hợp những
bằng cách sử dụng quá trình tương tự

109
00:05:14,680 --> 00:05:18,660
chúng tôi đã làm cho việc sáp nhập hai
và một trong những chỉ một thời gian trước đây.

110
00:05:18,660 --> 00:05:23,080
>> Nửa bên trái, nhỏ nhất
yếu tố trên nửa bên trái là năm.

111
00:05:23,080 --> 00:05:25,620
Các phần tử nhỏ nhất trên
nửa bên phải là một.

112
00:05:25,620 --> 00:05:27,370
Mà trong số đó là nhỏ hơn?

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

114
00:05:29,260 --> 00:05:32,250
>> Các phần tử nhỏ nhất trên
nửa bên trái là năm.

115
00:05:32,250 --> 00:05:35,540
Các phần tử nhỏ nhất trên
nửa bên phải là hai.

116
00:05:35,540 --> 00:05:36,970
Những gì là nhỏ nhất?

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

118
00:05:38,160 --> 00:05:41,540
Và rồi cuối cùng năm và
không có gì, chúng ta có thể nói năm.

119
00:05:41,540 --> 00:05:43,935
>> OK, hình ảnh quá lớn, chúng ta hãy
nghỉ ngơi cho một thứ hai

120
00:05:43,935 --> 00:05:46,080
và tìm ra nơi chúng ta đang có.

121
00:05:46,080 --> 00:05:48,580
Nếu chúng ta bắt đầu từ
khi bắt đầu, chúng tôi

122
00:05:48,580 --> 00:05:51,640
Hiện tại đã hoàn thành
mảng tổng chỉ

123
00:05:51,640 --> 00:05:53,810
một bước của mã giả ở đây.

124
00:05:53,810 --> 00:05:56,645
Chúng tôi đã sắp xếp các
nửa bên trái của mảng.

125
00:05:56,645 --> 00:05:59,490
>> Nhớ lại rằng ban đầu
Để lên năm, hai, một.

126
00:05:59,490 --> 00:06:02,570
Bằng cách đi qua quá trình này
và làm tổ xuống và lặp đi lặp lại,

127
00:06:02,570 --> 00:06:05,990
tiếp tục phá vỡ các vấn đề
thành nhiều phần nhỏ hơn và nhỏ hơn,

128
00:06:05,990 --> 00:06:09,670
bây giờ chúng tôi đã hoàn thành
bước một trong những giả

129
00:06:09,670 --> 00:06:13,940
cho mảng bắt đầu toàn bộ.

130
00:06:13,940 --> 00:06:16,670
Chúng tôi đã sắp xếp một nửa bên trái của nó.

131
00:06:16,670 --> 00:06:18,670
>> Vì vậy, bây giờ hãy đóng băng ở đó.

132
00:06:18,670 --> 00:06:23,087
Và bây giờ hãy sắp xếp đúng các
một nửa của mảng ban đầu.

133
00:06:23,087 --> 00:06:25,670
Và chúng ta sẽ làm điều đó bằng cách
đi qua cùng lặp đi lặp lại

134
00:06:25,670 --> 00:06:30,630
quá trình phá vỡ những điều xuống
và sau đó sáp nhập chúng lại với nhau.

135
00:06:30,630 --> 00:06:34,290
>> Vì vậy, nửa bên trái của
màu đỏ, hoặc nửa trái

136
00:06:34,290 --> 00:06:38,830
của nửa bên phải của bản gốc
mảng, tôi sẽ nói là ba.

137
00:06:38,830 --> 00:06:40,312
Một lần nữa, tôi là nhất quán ở đây.

138
00:06:40,312 --> 00:06:42,020
Nếu bạn có một kỳ lạ
số yếu tố, nó

139
00:06:42,020 --> 00:06:44,478
không thực sự quan trọng cho dù
bạn làm cho một trái nhỏ hơn

140
00:06:44,478 --> 00:06:45,620
hoặc phải một nhỏ hơn.

141
00:06:45,620 --> 00:06:49,230
>> Điều quan trọng là bất cứ khi nào bạn
gặp phải vấn đề này trong việc thực hiện

142
00:06:49,230 --> 00:06:51,422
một hợp nhất, bạn cần phải phù hợp.

143
00:06:51,422 --> 00:06:53,505
Bạn có thể luôn luôn cần phải
làm cho một bên trái nhỏ hơn

144
00:06:53,505 --> 00:06:55,421
hoặc luôn luôn cần phải thực hiện
phía bên phải nhỏ hơn.

145
00:06:55,421 --> 00:06:57,720
Ở đây, tôi đã chọn luôn
làm cho phía bên trái nhỏ hơn

146
00:06:57,720 --> 00:07:04,380
khi mảng của tôi, hoặc tôi
sub-array, là một kích thước lẻ.

147
00:07:04,380 --> 00:07:07,420
>> Ba là một yếu tố duy nhất,
và do đó, nó được sắp xếp.

148
00:07:07,420 --> 00:07:10,860
Chúng tôi đã thừa hưởng giả định rằng
trong suốt toàn bộ quá trình của chúng tôi cho đến nay.

149
00:07:10,860 --> 00:07:15,020
Vì vậy, bây giờ hãy sắp xếp đúng các
một nửa của nửa bên phải,

150
00:07:15,020 --> 00:07:18,210
hoặc nửa bên phải của màu đỏ.

151
00:07:18,210 --> 00:07:20,390
>> Một lần nữa, chúng ta cần phải phân chia này xuống.

152
00:07:20,390 --> 00:07:21,910
Đây không phải là một mảng yếu tố duy nhất.

153
00:07:21,910 --> 00:07:23,970
Chúng tôi không thể khai báo nó được sắp xếp.

154
00:07:23,970 --> 00:07:27,060
Và vì vậy đầu tiên, chúng ta sẽ
để sắp xếp một nửa trái.

155
00:07:27,060 --> 00:07:31,620
>> Nửa bên trái là một yếu tố duy nhất,
vì vậy nó loại theo mặc định.

156
00:07:31,620 --> 00:07:34,840
Sau đó chúng tôi sẽ sắp xếp quyền
một nửa, đó là một yếu tố duy nhất.

157
00:07:34,840 --> 00:07:41,250
Nó được sắp xếp theo mặc định. Và bây giờ,
chúng ta có thể kết hợp hai cùng nhau.

158
00:07:41,250 --> 00:07:45,820
Bốn là nhỏ hơn, và
sau đó sáu là nhỏ hơn.

159
00:07:45,820 --> 00:07:48,870
>> Một lần nữa, những gì chúng tôi đã thực hiện tại thời điểm này?

160
00:07:48,870 --> 00:07:52,512
Chúng tôi đã sắp xếp bên trái
một nửa của nửa bên phải.

161
00:07:52,512 --> 00:07:54,720
Hoặc sẽ trở lại với bản gốc
màu sắc mà ở đó,

162
00:07:54,720 --> 00:07:57,875
chúng tôi đã sắp xếp bên trái
một nửa màu đỏ nhẹ nhàng hơn.

163
00:07:57,875 --> 00:08:00,416
Ban đầu nó được một viên gạch tối
màu đỏ và bây giờ nó là một màu đỏ nhẹ nhàng hơn,

164
00:08:00,416 --> 00:08:02,350
hoặc nó là một màu đỏ nhẹ nhàng hơn.

165
00:08:02,350 --> 00:08:05,145
>> Và sau đó chúng tôi đã sắp xếp các
nửa bên phải của màu đỏ nhẹ nhàng hơn.

166
00:08:05,145 --> 00:08:08,270
Bây giờ, tốt, họ đang xanh một lần nữa, chỉ
bởi vì chúng ta đang trải qua một quá trình.

167
00:08:08,270 --> 00:08:10,720
Và chúng ta phải lặp lại
trên này và hơn.

168
00:08:10,720 --> 00:08:14,695
>> Vì vậy, bây giờ chúng tôi có thể kết hợp những
hai nửa lại với nhau.

169
00:08:14,695 --> 00:08:15,820
Và đó là những gì chúng tôi làm ở đây.

170
00:08:15,820 --> 00:08:17,653
Vì vậy, các đường màu đen chỉ
chia một nửa trái

171
00:08:17,653 --> 00:08:19,690
và nửa bên phải của phần loại này.

172
00:08:19,690 --> 00:08:24,310
>> Chúng tôi so sánh các giá trị nhỏ nhất
ở phía bên trái của array--

173
00:08:24,310 --> 00:08:26,710
hay tha thứ cho tôi, nhỏ nhất
giá trị của một nửa trái

174
00:08:26,710 --> 00:08:30,790
với giá trị nhỏ nhất của quyền
nửa và thấy rằng ba là nhỏ hơn.

175
00:08:30,790 --> 00:08:32,530
Và bây giờ là một chút của một tối ưu hóa, phải không?

176
00:08:32,530 --> 00:08:35,175
Có thực sự không có gì
còn lại ở phía bên trái.

177
00:08:35,175 --> 00:08:37,440
>> Không có gì còn lại là
ở bên trái,

178
00:08:37,440 --> 00:08:40,877
vì vậy chúng tôi có thể có hiệu quả
chỉ move-- chúng ta có thể khai báo

179
00:08:40,877 --> 00:08:42,960
phần còn lại của nó là thực sự
sắp xếp và chỉ tack nó

180
00:08:42,960 --> 00:08:45,126
trên, bởi vì không có gì
khác để so sánh.

181
00:08:45,126 --> 00:08:49,140
Và chúng ta biết rằng phía bên phải
của các bên phải được sắp xếp.

182
00:08:49,140 --> 00:08:52,770
>> OK, vì vậy bây giờ chúng ta hãy đóng băng một lần nữa và
tìm ra nơi chúng ta đang ở trong câu chuyện.

183
00:08:52,770 --> 00:08:56,120
Trong mảng tổng thể,
những gì chúng tôi đã thực hiện?

184
00:08:56,120 --> 00:08:58,790
Chúng tôi đã thực sự hoàn thành
Bây giờ bước một và bước hai.

185
00:08:58,790 --> 00:09:03,300
Chúng tôi sắp xếp một nửa trái, và
chúng tôi sắp xếp một nửa bên phải.

186
00:09:03,300 --> 00:09:08,210
>> Vì vậy, bây giờ, tất cả những gì còn lại là dành cho chúng tôi
kết hợp hai nửa lại với nhau.

187
00:09:08,210 --> 00:09:11,670
Vì vậy, chúng ta so sánh các giá trị thấp nhất
yếu tố của mỗi nửa của mảng

188
00:09:11,670 --> 00:09:13,510
lần lượt, và tham gia thảo luận.

189
00:09:13,510 --> 00:09:16,535
Một là ít hơn so với ba, vì vậy một trong những đi.

190
00:09:16,535 --> 00:09:19,770
>> Hai là ít hơn so với ba, vì vậy hai đi.

191
00:09:19,770 --> 00:09:22,740
Ba là ít hơn 5, do đó, ba đi.

192
00:09:22,740 --> 00:09:25,820
Bốn là ít hơn 5, do bốn đi.

193
00:09:25,820 --> 00:09:30,210
Sau đó năm là ít hơn sáu,
và sáu là tất cả những gì còn lại.

194
00:09:30,210 --> 00:09:31,820
>> Bây giờ, tôi biết, đó là rất nhiều bước.

195
00:09:31,820 --> 00:09:33,636
Và chúng tôi đã để lại rất nhiều
bộ nhớ trong thức của chúng tôi.

196
00:09:33,636 --> 00:09:35,260
Và đó là những gì những hình vuông màu xám.

197
00:09:35,260 --> 00:09:40,540
Và nó có thể cảm thấy như mất một
nhiều thời gian hơn sắp xếp chèn, bong bóng

198
00:09:40,540 --> 00:09:42,660
sắp xếp, hoặc sắp xếp chọn.

199
00:09:42,660 --> 00:09:45,330
>> Nhưng thực sự, bởi vì một
rất nhiều các quá trình

200
00:09:45,330 --> 00:09:48,260
đang xảy ra tại các time-- cùng
đó là cái gì chúng ta sẽ thấy, một lần nữa,

201
00:09:48,260 --> 00:09:51,100
nói về khi chúng ta nói về
đệ quy trong một tương lai video--

202
00:09:51,100 --> 00:09:53,799
thuật toán này thực sự
rõ ràng là cơ bản

203
00:09:53,799 --> 00:09:55,590
khác với bất cứ điều gì
chúng ta đã thấy trước

204
00:09:55,590 --> 00:09:58,820
nhưng cũng là đáng kể
hiệu quả hơn.

205
00:09:58,820 --> 00:09:59,532
>> Tại sao vậy?

206
00:09:59,532 --> 00:10:01,240
Vâng, trong tồi tệ nhất
trường hợp kịch bản, chúng tôi có

207
00:10:01,240 --> 00:10:04,830
chia n yếu tố lên
và sau đó kết hợp lại chúng.

208
00:10:04,830 --> 00:10:06,680
Nhưng khi chúng ta kết hợp lại
chúng, những gì chúng tôi đang làm

209
00:10:06,680 --> 00:10:11,110
về cơ bản là tăng gấp đôi
kích thước của mảng nhỏ hơn.

210
00:10:11,110 --> 00:10:14,260
Chúng tôi có một bó của một phần tử
mảng mà chúng ta có hiệu quả

211
00:10:14,260 --> 00:10:16,290
kết hợp thành hai mảng phần tử.

212
00:10:16,290 --> 00:10:18,590
Và sau đó chúng ta lấy những
hai mảng yếu tố

213
00:10:18,590 --> 00:10:21,890
và kết hợp chúng lại với nhau thành
bốn mảng phần tử, và như vậy,

214
00:10:21,890 --> 00:10:26,130
và như vậy, và như vậy, cho đến khi chúng tôi
có một mảng n phần tử duy nhất.

215
00:10:26,130 --> 00:10:29,910
>> Nhưng làm thế nào nhiều trùng lặp
nó đi để có được để n?

216
00:10:29,910 --> 00:10:31,460
Hãy suy nghĩ lại với ví dụ danh bạ điện thoại.

217
00:10:31,460 --> 00:10:34,490
Đã bao nhiêu lần chúng ta phải xé
danh bạ điện thoại trong một nửa, như thế nào nhiều hơn nữa

218
00:10:34,490 --> 00:10:38,370
lần làm chúng ta phải xé cuốn sách điện thoại
một nửa, nếu kích thước của cuốn sách điện thoại

219
00:10:38,370 --> 00:10:39,680
tăng gấp đôi?

220
00:10:39,680 --> 00:10:41,960
Có chỉ là một, phải không?

221
00:10:41,960 --> 00:10:45,360
>> Vì vậy, có một số loại
yếu tố logarit đây.

222
00:10:45,360 --> 00:10:48,590
Nhưng chúng ta cũng vẫn phải có ít nhất
xem xét tất cả các yếu tố n.

223
00:10:48,590 --> 00:10:53,860
Vì vậy, trong trường hợp xấu nhất,
hợp nhất phân loại chạy trong n log n.

224
00:10:53,860 --> 00:10:56,160
Chúng ta phải nhìn vào
tất cả các yếu tố n,

225
00:10:56,160 --> 00:11:02,915
và chúng ta phải kết hợp chúng
với nhau trong log n bộ các bước.

226
00:11:02,915 --> 00:11:05,290
Trong trường hợp tốt nhất,
mảng được sắp xếp một cách hoàn hảo.

227
00:11:05,290 --> 00:11:06,300
Thật tuyệt.

228
00:11:06,300 --> 00:11:09,980
Nhưng dựa trên các thuật toán chúng ta có ở đây,
chúng ta vẫn phải tách ra và tái kết hợp.

229
00:11:09,980 --> 00:11:13,290
Mặc dù trong trường hợp này,
recombining là loại không có hiệu quả.

230
00:11:13,290 --> 00:11:14,720
Nó không phải là cần thiết.

231
00:11:14,720 --> 00:11:17,580
Nhưng chúng tôi vẫn đi qua
toàn bộ quá trình anyway.

232
00:11:17,580 --> 00:11:21,290
>> Vì vậy, trong trường hợp tốt nhất
và trong trường hợp xấu nhất,

233
00:11:21,290 --> 00:11:24,970
thuật toán này chạy trong n log n lần.

234
00:11:24,970 --> 00:11:29,130
Hợp nhất phân loại chắc chắn là một chút phức tạp hơn
hơn so với các thuật toán phân loại chính khác

235
00:11:29,130 --> 00:11:33,470
chúng tôi đã nói chuyện về CS50 nhưng là
đáng kể mạnh hơn.

236
00:11:33,470 --> 00:11:35,400
>> Và do đó, nếu bạn đã bao giờ tìm thấy
Nhân dịp cần đến nó

237
00:11:35,400 --> 00:11:38,480
hoặc sử dụng nó để sắp xếp một
tập hợp dữ liệu lớn, nhận được

238
00:11:38,480 --> 00:11:41,940
đầu của bạn xung quanh ý tưởng của đệ quy
là có được thực sự mạnh mẽ.

239
00:11:41,940 --> 00:11:45,270
Và nó sẽ làm cho bạn
chương trình thực sự hiệu quả hơn

240
00:11:45,270 --> 00:11:48,700
sử dụng hợp nhất phân loại so với bất cứ điều gì khác.

241
00:11:48,700 --> 00:11:49,640
Tôi Doug Lloyd.

242
00:11:49,640 --> 00:11:51,970
Đây là CS50.

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