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
>> डौग लॉयड: ठीक है, तो कोई मर्ज
क्रमबद्ध अभी तक एक एल्गोरिथ्म है

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
सरणी के बाईं आधा सॉर्ट
एन संभालने 1 से अधिक है।

16
00:00:46,320 --> 00:00:49,980
और मुझे लगता है जब मैं कहता हूँ क्या मतलब
एन संभालने 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
हम इस धारणा है कि leveraged है
हमारी पूरी प्रक्रिया के दौरान अब तक।

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
और इतने पर, और इतने पर, हम जब तक
एक भी एन तत्व सरणी है।

215
00:10:26,130 --> 00:10:29,910
>> लेकिन कितने दोहरीकरण
यह 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 लॉग एन में चलाता विलय।

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 लॉग एन समय में चलाता है।

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