[संगीत बजाना] 

डौग लॉयड: ठीक है, तो कोई मर्ज क्रमबद्ध अभी तक एक एल्गोरिथ्म है हम को सुलझाने के लिए उपयोग कर सकते हैं एक सरणी के तत्वों। हम देखेंगे लेकिन, जैसा कि यह मिल गया है एक बहुत बुनियादी फर्क चयन प्रकार, बुलबुला से प्रकार, और प्रविष्टि प्रकार कि यह वास्तव में बहुत चतुर हैं। 

मर्ज के पीछे मूल विचार क्रमबद्ध छोटे सरणियों सुलझाने के लिए है और फिर उन सरणियों गठबंधन एक साथ, या them-- विलय इसलिए सॉर्ट क्रम में name--। क्रमबद्ध करता विलय उस तरह से यह एक उपकरण के लाभ से है क्या है, जो प्रत्यावर्तन बुलाया हम जल्द ही के बारे में बात करने जा रहे हैं लेकिन हम वास्तव में अभी तक के बारे में बात नहीं की है। 

यहाँ मर्ज प्रकार के पीछे मूल विचार है। सरणी के बाईं आधा सॉर्ट एन संभालने 1 से अधिक है। और मुझे लगता है जब मैं कहता हूँ क्या मतलब एन संभालने 1 है, की तुलना में अधिक होता है मुझे लगता है हम मान सकते हैं कि लगता है कि एक सरणी यदि केवल एक ही तत्व होते हैं, यह हल है। हम वास्तव में जरूरत नहीं है यह करने के लिए कुछ भी करने को। हम सिर्फ यह हल किया जाना घोषणा कर सकते हैं। यह केवल एक ही तत्व है। 

तो स्यूडोकोड, फिर से, सरणी के बाईं आधे से सुलझाने तो ठीक आधे सरणी प्रकार, फिर एक साथ दो हिस्सों विलय। अब, पहले से ही आप हो सकता है सोच रही है, यह एक तरह से बस the-- आप टाल रहे हैं की तरह लगता है आप वास्तव में कुछ भी नहीं कर रहे हैं। आप बाईं को सॉर्ट कह रहे हैं आधा, ठीक आधे से तरह, लेकिन आप नहीं कह रहे हैं मुझे कैसे आप यह कर रहे हैं। 

लेकिन जब तक कि के रूप में याद एक सरणी एक ही तत्व है, हम इसे हल घोषणा कर सकते हैं। तो हम बस उन्हें एक साथ गठबंधन कर सकते हैं। और कहा कि वास्तव में है मर्ज प्रकार के पीछे मूल विचार है, इतना है कि इसे नीचे तोड़ने के लिए है अपने सरणियों आकार एक के हैं। और फिर तुम वहाँ से पुनर्निर्माण। 

क्रमबद्ध निश्चित रूप से है मर्ज एक जटिल एल्गोरिथ्म। और यह भी एक छोटी सी है कल्पना करने के लिए जटिल है। तो उम्मीद है, दृश्य है कि मैं आप के साथ पालन करने में मदद करेगा यहाँ है। और मैं चीजों को बयान करने के लिए अपनी पूरी कोशिश करेंगे और यह एक छोटे से अधिक के माध्यम से आगे बढ़ना धीरे-धीरे अन्य लोगों की तुलना में बस उम्मीद है कि अपने सिर को पाने के लिए मर्ज प्रकार के पीछे विचारों के आसपास। 

इसलिए हम के रूप में ही सरणी है अन्य छँटाई एल्गोरिथ्म वीडियो तुम्हें देखा है, तो them-- एक छह तत्व सरणी। और यहाँ हमारे स्यूडोकोड कोड प्रकार है बाईं आधा, ठीक आधे से तरह, एक साथ दो हिस्सों विलय। तो चलो इस बहुत ही गहरे लाल ईंट ले चलो सरणी और यह की बाईं आधा तरह। 

कुछ समय के लिए तो, हम जा रहे हैं सही पर सामान की अनदेखी करने के लिए। यह वहाँ है, लेकिन हम कर रहे हैं नहीं अभी तक उस कदम पर। हम नहीं कर रहे हैं पर क्रमबद्ध सरणी के ठीक आधे। हम की तरह छोड़ दिया पर रहे सरणी का आधा। और बस खातिर के एक छोटे से अधिक किया जा रहा है स्पष्ट है, तो मैं उल्लेख कर सकते हैं क्या कदम के लिए हम पर हैं, मैं स्विच करने के लिए जा रहा हूँ नारंगी के लिए इस सेट का रंग। अब, हम अभी भी बारे में बात कर रहे हैं मूल सरणी के एक ही बाईं आधा। लेकिन मैं करने में सक्षम होने से उम्मीद कर रहा हूँ विभिन्न मदों के रंग का उल्लेख है, यह एक छोटे से अधिक कर दूँगा यहाँ पर क्या हो रहा है साफ़ करें। 

ठीक है, तो अब हमारे पास एक तीन तत्व सरणी। हम इस के बाईं आधा सुलझाने के कैसे करते हैं अभी भी इस कदम है जो सरणी,? हम छोड़ सुलझाने की कोशिश कर रहे हैं ईंट लाल array-- के आधे बाएं जिनमें से आधे मैं अब नारंगी रंग गए हैं। 

ठीक है, हम कोशिश करते हैं और कर सकता है फिर से इस प्रक्रिया को दोहराएँ। तो हम में अब भी कर रहे सुलझाने की कोशिश के बीच पूरी सरणी के बाईं आधा। के बाईं आधा सरणी, मैं तो बस जा रहा हूँ मनमाने ढंग से तय करने के लिए कि बाईं आधा ठीक आधे से छोटा होगा, इस के लिए होता है, क्योंकि तीन तत्वों से मिलकर बनता है। 

और इसलिए मुझे लगता है कि कहने के लिए जा रहा हूँ बाईं आधा सरणी के बाईं आधा सिर्फ तत्व पाँच है। पांच, एक ही तत्व जा रहा है सरणी, हम इसे सुलझाने के लिए कैसे पता है। और तो पाँच हल है। हम सिर्फ इतना है कि घोषणा करने के लिए जा रहे हैं। यह एक ही तत्व सरणी है। 

तो क्या अब हम हल किया है, बाएं half-- के बाईं आधा या यों कहें, हम हल किया है, नारंगी के बाईं आधा। तो अब, क्रम में करने के लिए अभी भी पूरा समग्र सरणी के बाईं आधा, हम ठीक आधे से सुलझाने की जरूरत नारंगी, या इस सामान की। हम इसे कैसे करते हैं? खैर, हम एक दो तत्व सरणी है। तो हम छोड़ दिया आधे तरह कर सकते हैं दो है जो सरणी, के। दो एक ही तत्व है। तो यह डिफ़ॉल्ट रूप से हल है। तो फिर हम सही आधा तरह कर सकते हैं सरणी, एक के उस हिस्से का। यही कारण है कि डिफ़ॉल्ट रूप से की तरह है। 

अब यह पहली बार है हम एक मर्ज कदम पहुँच गए हैं। हम हालांकि, पूरा कर लिया है हम अब एक तरह से down-- नेस्ट रहे और कहा कि मुश्किल की तरह है प्रत्यावर्तन के साथ बात है, आप अपने रखने की जरूरत हम कर रहे हैं, जहां के बारे में सिर। तो हम छोड़ दिया की तरह है नारंगी हिस्से का आधा। 

और अब, हम छँटाई के बीच में हैं नारंगी हिस्से के ठीक आधे। और कहा कि इस प्रक्रिया में, हम कर रहे हैं कदम पर होने के बारे में अब, एक साथ दो हिस्सों विलय। हम दो हिस्सों में जब देखो सरणी की, हम दो और एक देखते हैं। कौन सा तत्व छोटा होता है? एक। 

फिर जो तत्व छोटा होता है? खैर, यह दो या कुछ भी नहीं है। तो यह दो है। तो अब, बस फिर फ्रेम करने के लिए हम संदर्भ में हैं, जहां हम हल किया है नारंगी के बाईं आधा और मूल के ठीक आधे। मैं मैं रंग बदल गया है पता हम कहाँ थे फिर, लेकिन लगता है कि है। और कारण है कि मैं इस किया था इस प्रक्रिया है क्योंकि है नीचे पुनरावृति जा रहा रखने के लिए जा रहा है। हम छोड़ हल किया है, पूर्व नारंगी के आधे और पूर्व नारंगी के ठीक आधे। 

अब, हम उन विलय करने की जरूरत है एक साथ भी दो हिस्सों। यही कारण है कि हम पर हैं कदम है। तो हम में से सभी पर विचार अब हरा कर रहे हैं कि तत्वों, मूल सरणी के बाईं आधा। और हम उन विलय उसी प्रक्रिया का उपयोग हम दो विलय के लिए किया था और एक बस एक पल पहले। 

बाईं आधा, छोटी बाईं आधे पर तत्व पाँच है। छोटी तत्व पर ठीक आधे से एक है। उन में से कौन सा छोटा होता है? एक। 

छोटी तत्व पर बाईं आधा पाँच है। छोटी तत्व पर ठीक आधे दो है। छोटी से छोटी क्या है? दो। और फिर अंत में पांच और कुछ भी नहीं है, हम पांच कह सकते हैं। 

ठीक है, तो बड़ी तस्वीर, चलो एक पल के लिए एक ब्रेक ले हम कहाँ हैं और यह पता लगाने की। हम से शुरू कर दिया है बहुत शुरुआत में, हम अब के लिए पूरी कर ली है समग्र सरणी बस यहां स्यूडोकोड कोड का एक कदम है। हम हल किया है सरणी के बाईं आधा। 

मूल याद है कि आदेश में पांच, दो, एक था। इस प्रक्रिया के माध्यम से जा रहा द्वारा और नीचे घोंसले के शिकार और दोहरा, समस्या को तोड़ने के लिए जारी नीचे और छोटे छोटे भागों में, हम अब पूरा कर लिया है स्यूडोकोड से एक कदम पूरे शुरुआती सरणी के लिए। हम अपनी बाईं आधा हल किया है। 

तो अब वहाँ फ्रीज करते हैं। और अब सही तरह चलो मूल सरणी का आधा। और हम ने ऐसा करने के लिए जा रहे हैं एक ही चलने के माध्यम से जा रहा बातें नीचे तोड़ने की प्रक्रिया और फिर उन्हें एक साथ विलय। 

तो के बाईं आधा लाल या बाईं आधा मूल के ठीक आधे से सरणी, मैं कहने जा रहा हूँ तीन है। फिर, मैं यहां लगातार की जा रही हूँ। आप एक अजीब है, तो तत्वों की संख्या, यह वास्तव में कोई फर्क नहीं पड़ता तुम छोड़ एक छोटा करने के या सही एक छोटे। 

क्या मायने रखता है, जब भी आपको लगता है कि के संचालन में इस समस्या का सामना एक मर्ज, आप अनुरूप होना चाहिए। आप या तो हमेशा की जरूरत है एक बाईं ओर छोटे बनाने या हमेशा बनाने की जरूरत है दाईं ओर छोटे। यहाँ, मैं हमेशा के लिए चुना है बाईं ओर छोटे बनाने जब मेरी सरणी, या मेरे उप-सरणी, एक अजीब आकार का है। 

तीन एक ही तत्व है, और इसलिए यह हल है। हम इस धारणा है कि leveraged है हमारी पूरी प्रक्रिया के दौरान अब तक। तो अब सही तरह चलो ठीक आधे के आधे से, या लाल के ठीक आधे। 

फिर, हम यह नीचे विभाजित करने की जरूरत है। यह एक ही तत्व सरणी नहीं है। हम इसे हल की घोषणा नहीं कर सकते हैं। और इसलिए सबसे पहले, हम जा रहे हैं बाईं आधे से सुलझाने के लिए। 

बाईं आधा एक ही तत्व है, इसलिए यह डिफ़ॉल्ट रूप से की तरह है। तो फिर हम सही तरह करने के लिए जा रहे हैं एक ही तत्व है जो आधे,। यह डिफ़ॉल्ट रूप से हल है। और अब, हम एक साथ उन दो विलय कर सकते हैं। चार छोटी है, और फिर छह छोटा होता है। 

फिर, क्या हम इस बिंदु पर किया है? हम छोड़ हल किया है, ठीक आधे का आधा। या मूल करने के लिए वापस जा रहा वहाँ थे कि रंग, हम बाईं हल किया है, नरम लाल का आधा। यह मूल रूप से एक अंधेरे ईंट था लाल और अब यह एक नरम लाल है, या यह एक नरम लाल था। 

और फिर हम हल किया है, नरम लाल के ठीक आधे। अब, ठीक है, वे सिर्फ फिर से हरे हो हम एक प्रक्रिया के माध्यम से जा रहे हैं क्योंकि। और हम दोहराने के लिए है इस पर और अधिक। 

तो अब हम उन विलय कर सकते हैं एक साथ दो हिस्सों। और कहा कि हम यहां क्या करते हैं। काला लाइन तो बस बाईं आधा विभाजित और इस तरह के हिस्से के ठीक आधे। 

हम छोटी मूल्य की तुलना array-- की बाईं ओर या मुझे माफ करना, छोटी बाईं आधे का मूल्य सही छोटे मूल्य के लिए आधा और तीन छोटी है कि लगता है। और अब एक अनुकूलन का एक सा है, है ना? कुछ भी नहीं है वास्तव में नहीं है बाईं ओर रवाना हो गए। 

शेष कुछ भी नहीं है बायीं ओर, इसलिए हम कुशलतापूर्वक कर सकते हैं बस हम घोषणा कर सकते हैं move-- यह बाकी वास्तव में है हल और सिर्फ यह हमले कुछ भी नहीं है, क्योंकि पर के खिलाफ तुलना करने के लिए कुछ और। और हम जानते हैं कि दाईं ओर दाईं ओर का हल है। 

ठीक है, तो अब हम फिर से जमा करते हैं और हम कहानी में हैं, जहां यह पता लगाने। समग्र सरणी में, हम क्या पूरा किया है? हम वास्तव में पूरा कर लिया है अब एक और कदम दो कदम। हम छोड़ आधा हल है, और हम सही आधा हल। 

तो अब, बनी हुई है कि हम सभी के लिए है एक साथ उन दो हिस्सों विलय करने के लिए। इसलिए हम सबसे कम मूल्यवान तुलना सरणी के प्रत्येक छमाही के तत्व और बदले में आगे बढ़ना है। एक से तीन की तुलना में कम है, तो एक हो जाता है। 

दो तीन से भी कम है, तो दो चला जाता है। तीन 5 से कम है, इसलिए तीन चला जाता है। चार 5 से कम है, तो चार चला जाता है। फिर पांच, छह से भी कम है और छह सब कि रहता है। 

अब, मुझे पता है, कि कदम की एक बहुत कुछ था। और हम एक बहुत छोड़ दिया है हमारे मद्देनजर स्मृति की। और उन है कि ग्रे वर्गों क्या कर रहे हैं। कि एक ले लिया और ऐसा शायद महसूस किया प्रविष्टि प्रकार की तुलना में अब बहुत कुछ है, बुलबुला तरह, या चयन तरह। 

लेकिन वास्तव में, क्योंकि एक इन प्रक्रियाओं के बहुत एक ही time-- पर हो रही हैं जो, फिर से, हम करेंगे कुछ है हम के बारे में बात करते हैं, जब इस बारे में बात एक भविष्य में प्रत्यावर्तन video-- वास्तव में इस एल्गोरिथ्म स्पष्ट रूप से मौलिक है कुछ से अलग हम पहले देखा है लेकिन काफी भी है अधिक कुशल। 

ऐसा क्यों? खैर, सबसे खराब में स्थिति यह है कि, हमारे पास n तत्वों को विभाजित करने के लिए और फिर उन्हें recombine। लेकिन हम recombine जब उन्हें, कि हम क्या कर रहे हैं मूल रूप से दोगुनी है छोटे सरणियों का आकार। हम एक तत्व का एक गुच्छा है सरणियों कि हम प्रभावी रूप से दो तत्व सरणियों में गठबंधन। और फिर हम उन ले दो तत्व सरणियों और में उन्हें एक साथ गठबंधन इतने पर चार तत्व सरणियों, और, और इतने पर, और इतने पर, हम जब तक एक भी एन तत्व सरणी है। 

लेकिन कितने दोहरीकरण यह n करने के लिए ले करता है? वापस फोन की किताब उदाहरण के लिए सोचो। कितनी बार हम आंसू के लिए क्या है छमाही में फोन पुस्तक, कितने अधिक कई बार हम फोन की किताब आंसू के लिए क्या है छमाही में, यदि फोन की किताब का आकार दोगुनी हो? सिर्फ एक, सही है? 

तो किसी प्रकार का है यहां लघुगणक तत्व। लेकिन हम यह भी अभी भी करने के लिए कम से कम n तत्वों के सभी को देखो। , सबसे बुरी स्थिति में तो क्रमबद्ध n लॉग एन में चलाता विलय। हम को देखने के लिए n तत्वों के सभी, और हम उन्हें गठबंधन करने के लिए है एक साथ लॉग n कदम के सेट में। बेहतरीन परिदृश्य में, सरणी पूरी तरह से हल है। यह बहुत अच्छा है। लेकिन एल्गोरिथ्म पर आधारित हम यहाँ है हम अभी भी विभाजित है और recombine के लिए है। इस मामले में हालांकि, recombining अप्रभावी की तरह है। यह आवश्यक नहीं है। लेकिन हम अभी भी माध्यम से जाना वैसे भी पूरी प्रक्रिया। 

सबसे अच्छा मामले में तो और सबसे खराब स्थिति में, इस एल्गोरिथ्म n लॉग एन समय में चलाता है। क्रमबद्ध मर्ज निश्चित रूप से थोड़ा पेचीदा मामला है अन्य मुख्य छँटाई एल्गोरिदम से हम CS50 के बारे में बात की है, लेकिन किया है काफी अधिक शक्तिशाली है। 

और अगर ऐसा है तो आप कभी भी मिल अवसर की जरूरत है इसे करने के लिए या एक तरह से करने के लिए इसका इस्तेमाल करने के लिए बड़े डेटा सेट, हो रही है प्रत्यावर्तन के विचार के आसपास अपने सिर वास्तव में शक्तिशाली होने जा रहा है। और इसे बनाने के लिए जा रहा है अपने कार्यक्रम वास्तव में बहुत अधिक कुशल कुछ और बनाम तरह विलय का उपयोग कर। मैं डौग लॉयड हूँ। इस CS50 है।