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
>> DOUG 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
>> ดังนั้น pseudocode อีกครั้งเป็น
เรียงลำดับครึ่งด้านซ้ายของอาร์เรย์

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
และรหัส pseudocode ของเราที่นี่คือการจัดเรียง
ครึ่งซ้ายจัดเรียงครึ่งขวา

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
หนึ่งในขั้นตอนของรหัส pseudocode ที่นี่

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
เราได้เสร็จสิ้นในขณะนี้
ขั้นตอนที่หนึ่ง pseudocode

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
การแยกองค์ประกอบ n ขึ้น
และจากนั้นพวกเขา recombine

208
00:10:04,830 --> 00:10:06,680
แต่เมื่อเรา recombine
พวกเขาสิ่งที่เรากำลังทำ

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
และอื่น ๆ และอื่น ๆ จนเรา
มีอาร์เรย์องค์ประกอบ n เดียว

215
00:10:26,130 --> 00:10:29,910
>> แต่กี่ doublings
มันจะใช้เวลาที่จะได้รับ n?

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
แต่เราก็ยังคงมีอย่างน้อย
ดูทุกองค์ประกอบที่ n

223
00:10:48,590 --> 00:10:53,860
ดังนั้นในสถานการณ์กรณีที่เลวร้ายที่สุด
ผสานการจัดเรียงทำงานใน n ล็อก n

224
00:10:53,860 --> 00:10:56,160
เราต้องมองไปที่
ทุกองค์ประกอบ n ที่

225
00:10:56,160 --> 00:11:02,915
และเราจะต้องรวมพวกเขา
ร่วมกันในชุด n เข้าสู่ระบบของขั้นตอน

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
แต่ขึ้นอยู่กับขั้นตอนวิธีการที่เรามีที่นี่
เรายังคงต้องแยกและ recombine

229
00:11:09,980 --> 00:11:13,290
ถึงแม้ว่าในกรณีนี้
recombining เป็นชนิดของการไม่ได้ผล

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
ขั้นตอนวิธีการนี​​้จะทำงานในบันทึก n n เวลา

234
00:11:24,970 --> 00:11:29,130
ผสานการเรียงลำดับแน่นอนบิต trickier
กว่าขั้นตอนวิธีการเรียงลำดับหลักอื่น ๆ

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