मर्ज एल्गोरिथम: Difference between revisions

Latest revision as of 16:06, 30 October 2023

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

आवेदन

मर्ज सॉर्ट के लिए उदाहरण

मर्ज एल्गोरिथ्म मर्ज सॉर्ट एल्गोरिथ्म में महत्वपूर्ण भूमिका निभाता है, तुलना-आधारित सॉर्टिंग एल्गोरिदम वैचारिक रूप से, मर्ज सॉर्ट एल्गोरिथम में दो चरण होते हैं।

पुनरावर्तन (कंप्यूटर विज्ञान) सूची को समान लंबाई की उपसूचियों में विभाजित करता है, जब तक कि प्रत्येक उपसूची में केवल तत्व न हो, या पुनरावृत्त (नीचे ऊपर) मर्ज सॉर्ट की स्थिति में, n उप-सूचियों के रूप में n तत्वों की सूची पर विचार करें। 1 आकार के परिभाषा के अनुसार, एकल तत्व वाली सूची को क्रमबद्ध किया जाता है।
जब तक एकल सूची में सभी तत्व सम्मिलित नहीं हो जाते, तब तक नई क्रमबद्ध सबलिस्ट बनाने के लिए बार-बार सब्लिस्ट्स को विलय करें। एकल सूची क्रमबद्ध सूची है।

मर्ज सॉर्ट एल्गोरिथम में मर्ज एल्गोरिथ्म का बार-बार उपयोग किया जाता है।

उदाहरण में मर्ज सॉर्ट का उदाहरण दिया गया है। यह 7 पूर्णांकों की अवर्गीकृत सारणी से प्रारम्भ होता है। सारणी को 7 विभाजनों में विभाजित किया गया है; प्रत्येक विभाजन में 1 तत्व होता है एवं इसे क्रमबद्ध किया जाता है। तब चयन गए विभाजनों को बड़ा, क्रमबद्ध, विभाजन बनाने के लिए विलय कर दिया जाता है, जब तक कि 1 विभाजन, क्रमबद्ध सारणी, शेष न रह जाए।

दो सूचियों को विलय करना

दो क्रमबद्ध सूचियों को विलय करना रैखिक समय एवं रैखिक या स्थिर स्थान (डेटा एक्सेस मॉडल के आधार पर) में किया जा सकता है। निम्नलिखित स्यूडोकोड एल्गोरिथम प्रदर्शित करता है, जो इनपुट सूचियों (या तो लिंक्ड सूचियों या सारणी डेटा संरचना) को विलय करता है, $A$ एवं $B$ नई सूची $C$ में^[1]^[2]^: 104 कार्यक्रम head सूची का प्रथम तत्व उत्पन्न करता है; किसी तत्व को त्यागने का अर्थ है कि इसे सूची से सामान्यतः पॉइंटर या इंडेक्स को बढ़ाकर विस्थापित करना है ।

algorithm merge(A, B) is
    inputs A, B : list
    returns list

    C := new empty list
    while A is not empty and B is not empty do
        if head(A) ≤ head(B) then
            append head(A) to C
            drop the head of A
        else
            append head(B) to C
            drop the head of B

    // By now, either A or B is empty. It remains to empty the other input list.
    while A is not empty do
        append head(A) to C
        drop the head of A
    while B is not empty do
        append head(B) to C
        drop the head of B
        return C

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

प्रसूची वरण एल्गोरिथम में, यह सबरूटीन सामान्यतः दो उप-सरणियों को विलय करने के लिए उपयोग किया जाता है A[lo..mid], A[mid+1..hi] एकल सारणी का यह उप-सरणियों A को अस्थायी सारणी में कॉपी करके, ऊपर विलय एल्गोरिथ्म को प्रारम्भ करके किया जा सकता है।^[1] अस्थायी सारणी के आवंटन से बचा जा सकता है, किन्तु गति एवं प्रोग्रामिंग सरलता के मूल्य पर विभिन्न स्थान में विलय एल्गोरिदम प्रस्तुत किए गए हैं,^[3] कभी-कभी उत्पादन करने के लिए रैखिक-समयबद्धता का त्याग करना $O (n log n)$ एल्गोरिथम;^[4] देखना प्रसूची वरण § रूपांतर विषय के लिए होता है।

के-वे विलीनीकरण

$k$ -वे विलीनीकरण बाइनरी विलीनीकरण को मनमाना संख्या में सामान्यीकृत करता है, $k$ क्रमबद्ध इनपुट सूचियों के आवेदन $k$ -वे विलीनीकरण विभिन्न वर्गीकृत एल्गोरिदम में उत्पन्न होती है, जिसमें धैर्य वर्गीकृत भी सम्मिलित है^[5] एवं बाहरी वर्गीकृत एल्गोरिथ्म जो इसके इनपुट $k = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/M − 1$ को विभाजित करता है, इन्हें चयनित करते हैं, इन ब्लॉक्स को विलय कर देते हैं।^[2]^{: 119–120}

इस समस्या के कई समाधान उपस्थित हैं। समाधान के ऊपर $k$ लूप करना है, प्रत्येक बार न्यूनतम तत्व के चयन के लिए सूचीबद्ध करता है, एवं इस लूप को तब तक दोहराता है जब तक कि सभी सूचियां रिक्त न हो जाएं।

इनपुट: की सूची $k$ सूचियाँ होती है।
जबकि कोई भी सूची रिक्त नहीं है।
- न्यूनतम प्रथम तत्व वाले का शोधन करने के लिए सूचियों पर लूप करें।
- न्यूनतम तत्व को आउटपुट करें और इसे उसकी सूची से विस्थापित कर दें।

सबसे उत्तम, सबसे निकृष्ट एवं औसत विषय $(k -1)(n - k / 2)$ यह एल्गोरिथ्म प्रदर्शन करता है, तत्वों की तुलना स्वयं कार्य को करने के लिए की जाती है तो कुल मिलाकर $n$ सूचियों में तत्व^[6] को प्राथमिकता कतार (डेटा संरचना) में उनके प्रथम तत्व द्वारा कुंजीबद्ध करके इसे सही किया जा सकता है।

कुंजी के रूप में प्रथम $k$ तत्व का उपयोग करके k सूचियों का न्यूनतम-सूचीबद्ध h बनाएँ।
जबकि कोई भी सूची रिक्त नहीं है।
- होने देना $i = find-min(h)$ .
- सूची का प्रथम तत्व आउटपुट करें $i$ एवं इसे इसको सूची से विस्थापित कर दें।
- पुनः h सूचीबद्ध $करें$ .

आउटपुट होने के लिए आगामी सबसे अल्प तत्व का शो करना एवं हीप ऑर्डर को पुनर्स्थापित करना $O (log k)$ में किया जा सकता है,^[6] एवं पूर्ण समस्या का समाधान किया जा सकता है।^[6]^[2]^{: 119–120}

समस्या के लिए तीसरा एल्गोरिथम विभाजन एवं जीत एल्गोरिथम समाधान है जो बाइनरी मर्ज एल्गोरिथम पर बनाता है।

यदि $k = 1$ , एकल इनपुट सूची का उत्पादन करें।
यदि $k = 2$ , बाइनरी मर्ज करें।
अन्यथा, पुनरावर्ती रूप से पूर्व मर्ज करें $⌊ k /2⌋$ सूचियाँ एवं अंतिम $⌈ k /2⌉$ सूचियाँ, बाइनरी इन्हें मर्ज करें।

जब इस एल्गोरिथम की इनपुट सूचियों को लंबाई के अनुसार क्रमबद्ध किया जाता है, तो सर्वप्रथम, इसके लिए इससे अर्घ्य की आवश्यकता होती है, $n ⌈log k ⌉$ तुलना अर्थात सूचीबद्ध आधारित एल्गोरिथम द्वारा उपयोग की जाने वाली संख्या के अर्ध से भी अर्घ्य व्यवहार में, यह सूचीबद्ध-आधारित एल्गोरिथम जितना तीव्र या मंद हो सकता है।^[6]

समानांतर विलय

बाइनरी मर्ज एल्गोरिथम का कार्य समानता संस्करण प्रसूची वरण समानांतर प्रसूची वरण के बिल्डिंग ब्लॉक के रूप में कार्य कर सकता है। निम्नलिखित स्यूडोकोड इस एल्गोरिथम को फोर्क-जॉइन मॉडल में प्रदर्शित करता है। समानांतर विभाजन एवं जीत शैली^[7]^: 800 यह दो क्रमबद्ध सारणीयो पर कार्य करता है, $A$ एवं $B$ क्रमबद्ध आउटपुट को सारणी में लिखता है, $C$ . अंकन A[i...j] का भाग दर्शाता है।

algorithm merge(A[i...j], B[k...ℓ], C[p...q]) is
    inputs A, B, C : array
           i, j, k, ℓ, p, q : indices

    let m = j - i,
        n = ℓ - k

    if m < n then
        swap A and B  // ensure that A is the larger array: i, j still belong to A; k, ℓ to B
        swap m and n

    if m ≤ 0 then
        return  // base case, nothing to merge

    let r = ⌊(i + j)/2⌋
    let s = binary-search(A[r], B[k...ℓ])
    let t = p + (r - i) + (s - k)
    C[t] = A[r]

    in parallel do
        merge(A[i...r], B[k...s], C[p...t])

merge(A[r+1...j], B[s...ℓ], C[t+1...q])

एल्गोरिथ्म या तो विभाजित करके संचालित होता है $A$ या $B$ , जो भी बड़ा हो, (लगभग) समान भागो में इसके पश्चात यह दूसरे सरणी को प्रथम के मध्य बिंदु से अल्प मान वाले भाग में एवं बड़े या समान मान वाले भाग में विभाजित करता है। अंत में, भागो की प्रत्येक जोड़ी विलय कर दी जाती है एवं एल्गोरिदम विजयी होते हैं, एवं चूंकि रिकर्सिव कॉल दूसरे से स्वतंत्र होते हैं, इसलिए उन्हें समानांतर में किया जा सकता है। हाइब्रिड दृष्टिकोण, जहां पुनरावर्तन आधार विषय के लिए सीरियल एल्गोरिदम का उपयोग किया जाता है, अभ्यास में अच्छा प्रदर्शन करने के लिए दिखाया गया है। ^[8] समांतर एल्गोरिदम का विश्लेषण एल्गोरिदम द्वारा कुल मिलाकर दो सारणी के लिए किया गया अवलोकन $n$ एलिमेंट्स, अर्थात $O (n)$ इसके सीरियल वर्जन का रनिंग टाइम है, यह तब से इष्टतम है $n$ तत्वों को कॉपी करने की आवश्यकता है $C$ . समांतर एल्गोरिदम के विश्लेषण की गणना करने के लिए एल्गोरिदम का अवलोकन, पुनरावृत्ति संबंध प्राप्त करना आवश्यक है। चूंकि विलय की दो रिकर्सिव कॉल समानांतर में हैं, केवल दो कॉलों के मूल्यवान होने पर विचार करने की आवश्यकता है। सबसे निकृष्ट स्थिति में, पुनरावर्ती कॉल में तत्वों की अधिकतम संख्या ${\textstyle {\frac {3}{4}}n}$ अधिकतम होती है, चूंकि अधिक तत्वों वाला सरणी अर्ध में पूर्ण रूप से विभाजित है। $\Theta \left(\log(n)\right)$ जोड़ना बाइनरी सर्च की वित्त, इस पुनरावृत्ति को ऊपरी सीमा के रूप में प्राप्त करते हैं।

समाधान $T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)$ है, $T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)$ , जिसका अर्थ है कि आदर्श मशीन पर असीमित संख्या में प्रोसेसर के साथ इतना समय लगता है।^[7]^{: 801–802}

$A$ एवं $B$ , वे इसमें इंटरलीव हो जाएंगे $C$ ; परिवर्तन भी $A$ एवं $B$ ऑर्डर को नष्ट कर देगा, यदि दोनों इनपुट सरणियों के मध्य समान आइटम विस्तृत हुए हैं। परिणामस्वरूप, जब विलय के लिए उपयोग किया जाता है, तो यह एल्गोरिथम ऐसा क्रम उत्पन्न करता है जो स्थिर नहीं होता है।

दो सूचियों का समानांतर विलय

ऐसे एल्गोरिदम भी हैं जो दो क्रमबद्ध सूचियों के विलय के एक उदाहरण के भीतर समानता का परिचय देते हैं। इनका उपयोग फील्ड-प्रोग्रामेबल गेट एरेज़ (FPGAs), विशेष सॉर्टिंग सर्किट के साथ-साथ आधुनिक प्रोसेसर में सिंगल-इंस्ट्रक्शन मल्टीपल-डेटा (SIMD) निर्देशों के साथ किया जा सकता है।

उपस्थिता समानांतर एल्गोरिदम या तो बिटोनिक सॉर्टर या सम-विषम विलय के भाग के संशोधनों पर आधारित हैं।^[9] ^[10] FPGAs के लिए, जो बहु-चक्र प्रतिक्रिया डेटापथ को विस्थापित करने पर केंद्रित था जो हार्डवेयर में कुशल पाइपलाइनिंग को रोकता था। इसके अतिरिक्त 2018 में, Papaphilippou P. et al। FLiMS प्रस्तुत की गयी ^[9]जिसने केवल आवश्यकता के द्वारा हार्डवेयर उपयोग एवं प्रदर्शन में सुधार किया $\log _{2}(P)+1$ के पाइपलाइन चरण $P/2$ की समानता के साथ विलय करने के लिए इकाइयों की तुलना एवं $P$ FPGA चक्र प्रति तत्व परिवर्तन किया।

भाषा समर्थन

कुछ कंप्यूटर भाषाएँ सॉर्ट किए गए संग्रह (सार डेटा प्रकार) को मर्ज करने के लिए अंतर्निहित या लाइब्रेरी समर्थन प्रदान करती हैं।

C ++

C ++ की मानक टेम्पलेट लाइब्रेरी में std::merge फ़ंक्शन है, जो पुनरावर्तकों की दो क्रमबद्ध श्रेणियों को मिलाता है, एवं std::inplace_merge, जो निरंतर दो क्रमबद्ध श्रेणियों को इन-प्लेस मर्ज करता है। इसके साथ में std::list (लिंक की गई सूची) वर्ग का स्वयं का merge है, विधि जो दूसरी सूची को स्वयं में विलीन कर देती है। विलय किए गए तत्वों के प्रकार को इससे अर्घ्य का समर्थन करना चाहिए, (<) ऑपरेटर, या इसे प्रथा तुलनित्र प्रदान किया जाना चाहिए।

C ++ 17 भिन्न-भिन्न निष्पादन नीतियों की अनुमति देता है, अर्थात् अनुक्रमिक, समांतर, एवं समांतर-अनुक्रमित होते है।^[11]

पायथन

पायथन (प्रोग्रामिंग लैंग्वेज) की मानक लाइब्रेरी (2.6 के पश्चात से) में भी a merge में कार्य करता है heapq मॉड्यूल, जो कई क्रमबद्ध पुनरावृत्तियों को लेता है, एवं उन्हें एकल पुनरावर्तक में मिला देता है।^[12]

यह भी देखें

विलय (संशोधन नियंत्रण)
जुड़ें (संबंधपरक बीजगणित)
जुड़ें (एसक्यूएल)
जुड़ें (यूनिक्स)

संदर्भ

↑ ^1.0 ^1.1 Skiena, Steven (2010). एल्गोरिथ्म डिजाइन मैनुअल (2nd ed.). Springer Science+Business Media. p. 123. ISBN 978-1-849-96720-4.
↑ ^2.0 ^2.1 ^2.2 Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. ISBN 978-3-540-77978-0.
↑ Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "प्रैक्टिकल इन-प्लेस मर्जसॉर्ट". Nordic J. Computing. 3 (1): 27–40. CiteSeerX 10.1.1.22.8523.
↑ Kim, Pok-Son; Kutzner, Arne (2004). सममित तुलना द्वारा स्थिर न्यूनतम संग्रहण विलय. European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723. CiteSeerX 10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN 978-3-540-23025-0.
↑ Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.
↑ ^6.0 ^6.1 ^6.2 ^6.3 Greene, William A. (1993). के-वे मर्जिंग और के-आरी सॉर्ट (PDF). Proc. 31-st Annual ACM Southeast Conf. pp. 127–135.
↑ ^7.0 ^7.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
↑ Victor J. Duvanenko (2011), "Parallel Merge", Dr. Dobb's Journal
↑ ^9.0 ^9.1 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: a Fast Lightweight 2-way Merger for Sorting". IEEE Transactions on Computers: 1–12. doi:10.1109/TC.2022.3146509. hdl:10044/1/95271.
↑ Saitoh, Makoto; Elsayed, Elsayed A.; Chu, Thiem Van; Mashimo, Susumu; Kise, Kenji (April 2018). "फीडबैक डेटापथ के बिना एक उच्च-प्रदर्शन और लागत प्रभावी हार्डवेयर मर्ज सॉर्टर". 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM): 197–204. doi:10.1109/FCCM.2018.00038.
↑ "std:merge". cppreference.com. 2018-01-08. Retrieved 2018-04-28.
↑ "heapq — Heap queue algorithm — Python 3.10.1 documentation".

अग्रिम पठन

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp. 197–207.

बाहरी संबंध

High Performance Implementation of Parallel and Serial Merge in C# with source in GitHub and in C++ GitHub

[skiena-1] 1.0 ^1.1 Skiena, Steven (2010). एल्गोरिथ्म डिजाइन मैनुअल (2nd ed.). Springer Science+Business Media. p. 123. ISBN 978-1-849-96720-4.

[toolbox-2] 2.0 ^2.1 ^2.2 Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. ISBN 978-3-540-77978-0.

[3] Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "प्रैक्टिकल इन-प्लेस मर्जसॉर्ट". Nordic J. Computing. 3 (1): 27–40. CiteSeerX 10.1.1.22.8523.

[4] Kim, Pok-Son; Kutzner, Arne (2004). सममित तुलना द्वारा स्थिर न्यूनतम संग्रहण विलय. European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723. CiteSeerX 10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN 978-3-540-23025-0.

[Chandramouli-5] Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.

[greene-6] 6.0 ^6.1 ^6.2 ^6.3 Greene, William A. (1993). के-वे मर्जिंग और के-आरी सॉर्ट (PDF). Proc. 31-st Annual ACM Southeast Conf. pp. 127–135.

[clrs-7] 7.0 ^7.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.

[vjd-8] Victor J. Duvanenko (2011), "Parallel Merge", Dr. Dobb's Journal

[flimsj-9] 9.0 ^9.1 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: a Fast Lightweight 2-way Merger for Sorting". IEEE Transactions on Computers: 1–12. doi:10.1109/TC.2022.3146509. hdl:10044/1/95271.

[10] Saitoh, Makoto; Elsayed, Elsayed A.; Chu, Thiem Van; Mashimo, Susumu; Kise, Kenji (April 2018). "फीडबैक डेटापथ के बिना एक उच्च-प्रदर्शन और लागत प्रभावी हार्डवेयर मर्ज सॉर्टर". 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM): 197–204. doi:10.1109/FCCM.2018.00038.

[11] "std:merge". cppreference.com. 2018-01-08. Retrieved 2018-04-28.

[12] "heapq — Heap queue algorithm — Python 3.10.1 documentation".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
 {{Short description|Algorithm that combines multiple sorted lists into one}}
-मर्ज [[कलन विधि]] एल्गोरिदम का एक परिवार है जो इनपुट के रूप में कई [[छँटाई एल्गोरिथ्म]] सूचियों को लेता है और आउटपुट के रूप में एकल सूची का उत्पादन करता है, जिसमें इनपुट सूची के सभी तत्व क्रमबद्ध क्रम में होते हैं। इन एल्गोरिदम का उपयोग विभिन्न सॉर्टिंग एल्गोरिदम में [[सबरूटीन]]्स के रूप में किया जाता है, सबसे प्रसिद्ध [[ मर्ज़ सॉर्ट ]]।
+'''मर्ज [[कलन विधि|एल्गोरिथम]]''', एल्गोरिदम का समूह है जो इनपुट के रूप में कई सॉर्ट एल्गोरिथ्म सूचियों को लेता है एवं आउटपुट के रूप में एकल सूची का उत्पादन करता है, जिसमें इनपुट सूची के सभी तत्व क्रमबद्ध क्रम में होते हैं। इन एल्गोरिदम का उपयोग विभिन्न सॉर्टिंग एल्गोरिदम में सबरूटीन के रूप में किया जाता है।
 == आवेदन ==
-[[File:Merge sort algorithm diagram.svg|thumb|upright=1.5|मर्ज सॉर्ट के लिए एक उदाहरण]]मर्ज एल्गोरिथ्म मर्ज सॉर्ट एल्गोरिथ्म में एक महत्वपूर्ण भूमिका निभाता है, एक तुलना सॉर्ट|तुलना-आधारित सॉर्टिंग एल्गोरिदम। वैचारिक रूप से, मर्ज सॉर्ट एल्गोरिथम में दो चरण होते हैं:
+[[File:Merge sort algorithm diagram.svg|thumb|upright=1.5|मर्ज सॉर्ट के लिए  उदाहरण]]मर्ज एल्गोरिथ्म मर्ज सॉर्ट एल्गोरिथ्म में महत्वपूर्ण भूमिका निभाता है, तुलना-आधारित सॉर्टिंग एल्गोरिदम वैचारिक रूप से, मर्ज सॉर्ट एल्गोरिथम में दो चरण होते हैं।
-# पुनरावर्तन (कंप्यूटर विज्ञान) सूची को (मोटे तौर पर) समान लंबाई की उपसूचियों में विभाजित करता है, जब तक कि प्रत्येक उपसूची में केवल एक तत्व न हो, या पुनरावृत्त (नीचे ऊपर) मर्ज सॉर्ट के मामले में, n उप-सूचियों के रूप में n तत्वों की सूची पर विचार करें आकार 1 का। परिभाषा के अनुसार, एकल तत्व वाली सूची को क्रमबद्ध किया जाता है।
+# पुनरावर्तन (कंप्यूटर विज्ञान) सूची को समान लंबाई की उपसूचियों में विभाजित करता है, जब तक कि प्रत्येक उपसूची में केवल तत्व न हो, या पुनरावृत्त (नीचे ऊपर) मर्ज सॉर्ट की स्थिति में, n उप-सूचियों के रूप में n तत्वों की सूची पर विचार करें। 1 आकार के परिभाषा के अनुसार, एकल तत्व वाली सूची को क्रमबद्ध किया जाता है।
-# जब तक एकल सूची में सभी तत्व शामिल नहीं हो जाते, तब तक एक नई क्रमबद्ध सबलिस्ट बनाने के लिए बार-बार सब्लिस्ट्स को मर्ज करें। एकल सूची क्रमबद्ध सूची है।
+# जब तक एकल सूची में सभी तत्व सम्मिलित नहीं हो जाते, तब तक नई क्रमबद्ध सबलिस्ट बनाने के लिए बार-बार सब्लिस्ट्स को विलय करें। एकल सूची क्रमबद्ध सूची है।
 मर्ज सॉर्ट एल्गोरिथम में मर्ज एल्गोरिथ्म का बार-बार उपयोग किया जाता है।
-उदाहरण में मर्ज सॉर्ट का उदाहरण दिया गया है। यह 7 पूर्णांकों की एक अवर्गीकृत सरणी से शुरू होता है। सरणी को 7 विभाजनों में विभाजित किया गया है; प्रत्येक विभाजन में 1 तत्व होता है और इसे क्रमबद्ध किया जाता है। तब छांटे गए विभाजनों को बड़ा, क्रमबद्ध, विभाजन बनाने के लिए विलय कर दिया जाता है, जब तक कि 1 विभाजन, क्रमबद्ध सरणी, शेष न रह जाए।
+उदाहरण में मर्ज सॉर्ट का उदाहरण दिया गया है। यह 7 पूर्णांकों की अवर्गीकृत सारणी से प्रारम्भ होता है। सारणी को 7 विभाजनों में विभाजित किया गया है; प्रत्येक विभाजन में 1 तत्व होता है एवं इसे क्रमबद्ध किया जाता है। तब चयन गए विभाजनों को बड़ा, क्रमबद्ध, विभाजन बनाने के लिए विलय कर दिया जाता है, जब तक कि 1 विभाजन, क्रमबद्ध सारणी, शेष न रह जाए।
-== दो सूचियों को मर्ज करना ==
+== दो सूचियों को विलय करना ==
-दो क्रमबद्ध सूचियों को एक में विलय करना [[रैखिक समय]] और रैखिक या स्थिर स्थान (डेटा एक्सेस मॉडल के आधार पर) में किया जा सकता है। निम्नलिखित [[स्यूडोकोड]] एक एल्गोरिथम प्रदर्शित करता है जो इनपुट सूचियों (या तो लिंक्ड सूचियों या [[सरणी डेटा संरचना]]) को मर्ज करता है {{mvar|A}} और {{mvar|B}} एक नई सूची में {{mvar|C}}.<ref name="skiena">{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title=एल्गोरिथ्म डिजाइन मैनुअल|publisher=[[Springer Science+Business Media]] |edition=2nd |year=2010 |isbn=978-1-849-96720-4 |page=123}}</ref>{{r|toolbox}}{{rp|104}} कार्यक्रम {{mono|head}} सूची का पहला तत्व उत्पन्न करता है; किसी तत्व को छोड़ने का मतलब है कि इसे सूची से हटाना, आमतौर पर पॉइंटर या इंडेक्स को बढ़ाकर।
+दो क्रमबद्ध सूचियों को विलय करना [[रैखिक समय]] एवं रैखिक या स्थिर स्थान (डेटा एक्सेस मॉडल के आधार पर) में किया जा सकता है। निम्नलिखित [[स्यूडोकोड]] एल्गोरिथम प्रदर्शित करता है, जो इनपुट सूचियों (या तो लिंक्ड सूचियों या [[सरणी डेटा संरचना|सारणी डेटा संरचना]]) को विलय करता है, {{mvar|A}} एवं {{mvar|B}} नई सूची {{mvar|C}} में<ref name="skiena">{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title=एल्गोरिथ्म डिजाइन मैनुअल|publisher=[[Springer Science+Business Media]] |edition=2nd |year=2010 |isbn=978-1-849-96720-4 |page=123}}</ref>{{r|toolbox}}{{rp|104}} कार्यक्रम {{mono|head}} सूची का प्रथम तत्व उत्पन्न करता है; किसी तत्व को त्यागने का अर्थ है कि इसे सूची से सामान्यतः पॉइंटर या इंडेक्स को बढ़ाकर विस्थापित करना है ।
-  एल्गोरिथम मर्ज (ए, बी) है
+  '''algorithm''' merge(A, B) '''is'''
-      इनपुट ए, बी: सूची
+      '''inputs''' A, B : list
-      रिटर्न सूची
+      '''returns''' list
-      सी: = नई खाली सूची
+      C := new empty list
-      जबकि A खाली नहीं है और B खाली नहीं है
+      '''while''' A is not empty and B is not empty '''do'''
-          अगर सिर (ए) ≤ सिर (बी) तो
+          '''if''' head(A) ≤ head(B) '''then'''
-              शीर्ष (A) को C से जोड़ें
+              append head(A) to C
-              ए का सिर गिरा दो
+              drop the head of A
-          अन्य
+          '''else'''
-              सिर (बी) को सी में जोड़ें
+              append head(B) to C
-              बी का सिर गिरा दो
+              drop the head of B
-      ''// अब तक, या तो ए या बी खाली है। यह अन्य इनपुट सूची को खाली करने के लिए बनी हुई है।''
+      ''// By now, either A or B is empty. It remains to empty the other input list.''
-      जबकि A खाली नहीं है
+      '''while''' A is not empty '''do'''
-          शीर्ष (A) को C से जोड़ें
+          append head(A) to C
-          ए का सिर गिरा दो
+          drop the head of A
-      जबकि B खाली नहीं है
+      '''while''' B is not empty '''do'''
-          सिर (बी) को सी में जोड़ें
+          append head(B) to C
-          बी का सिर गिरा दो
+          drop the head of B
+         '''return''' C
-     वापसी सी
-जब इनपुट लिंक्ड सूचियाँ हैं, तो इस एल्गोरिथम को केवल कार्य स्थान की एक स्थिर मात्रा का उपयोग करने के लिए लागू किया जा सकता है; सूचियों के नोड्स में पॉइंटर्स को बहीखाता पद्धति के लिए और अंतिम मर्ज की गई सूची के निर्माण के लिए पुन: उपयोग किया जा सकता है।
+जब इनपुट लिंक्ड सूचियाँ हैं, तो इस एल्गोरिथम को केवल कार्य स्थान की स्थिर मात्रा का उपयोग करने के लिए प्रारम्भ किया जा सकता है, सूचियों के ग्रंथि में संकेत को बहीखाता पद्धति के लिए एवं अंतिम विलय की गई सूची के निर्माण के लिए पुन: उपयोग किया जा सकता है।
-मर्ज सॉर्ट एल्गोरिथम में, यह सबरूटीन आमतौर पर दो उप-सरणियों को मर्ज करने के लिए उपयोग किया जाता है {{mono|A[lo..mid]}}, {{mono|A[mid+1..hi]}} एकल सरणी का {{mono|A}}. यह उप-सरणियों को एक अस्थायी सरणी में कॉपी करके, फिर ऊपर मर्ज एल्गोरिथ्म को लागू करके किया जा सकता है।{{r|skiena}} एक अस्थायी सरणी के आवंटन से बचा जा सकता है, लेकिन गति और प्रोग्रामिंग आसानी की कीमत पर। विभिन्न इन-प्लेस मर्ज एल्गोरिदम तैयार किए गए हैं,<ref>{{cite journal |last1=Katajainen |first1=Jyrki |first2=Tomi |last2=Pasanen |first3=Jukka |last3=Teuhola |title=प्रैक्टिकल इन-प्लेस मर्जसॉर्ट|journal=Nordic J. Computing |volume=3 |issue=1 |year=1996 |pages=27–40 |citeseerx=10.1.1.22.8523}}</ref> कभी-कभी उत्पादन करने के लिए रैखिक-समयबद्धता का त्याग करना {{math|''O''(''n'' log ''n'')}} कलन विधि;<ref>{{Cite conference| doi = 10.1007/978-3-540-30140-0_63| title = सममित तुलना द्वारा स्थिर न्यूनतम संग्रहण विलय| conference = European Symp. Algorithms| volume = 3221| pages = 714–723| series = Lecture Notes in Computer Science| year = 2004| last1 = Kim | first1 = Pok-Son| last2 = Kutzner | first2 = Arne| isbn = 978-3-540-23025-0| citeseerx=10.1.1.102.4612}}</ref> देखना {{slink|Merge sort|Variants}} चर्चा के लिए।
+प्रसूची वरण एल्गोरिथम में, यह सबरूटीन सामान्यतः दो उप-सरणियों को विलय करने के लिए उपयोग किया जाता है {{mono|A[lo..mid]}}, {{mono|A[mid+1..hi]}} एकल सारणी का यह उप-सरणियों {{mono|A}} को अस्थायी सारणी में कॉपी करके, ऊपर विलय एल्गोरिथ्म को प्रारम्भ करके किया जा सकता है।{{r|skiena}} अस्थायी सारणी के आवंटन से बचा जा सकता है, किन्तु गति एवं प्रोग्रामिंग सरलता के मूल्य पर विभिन्न स्थान में विलय एल्गोरिदम प्रस्तुत किए गए हैं,<ref>{{cite journal |last1=Katajainen |first1=Jyrki |first2=Tomi |last2=Pasanen |first3=Jukka |last3=Teuhola |title=प्रैक्टिकल इन-प्लेस मर्जसॉर्ट|journal=Nordic J. Computing |volume=3 |issue=1 |year=1996 |pages=27–40 |citeseerx=10.1.1.22.8523}}</ref> कभी-कभी उत्पादन करने के लिए रैखिक-समयबद्धता का त्याग करना {{math|''O''(''n'' log ''n'')}} एल्गोरिथम;<ref>{{Cite conference| doi = 10.1007/978-3-540-30140-0_63| title = सममित तुलना द्वारा स्थिर न्यूनतम संग्रहण विलय| conference = European Symp. Algorithms| volume = 3221| pages = 714–723| series = Lecture Notes in Computer Science| year = 2004| last1 = Kim | first1 = Pok-Son| last2 = Kutzner | first2 = Arne| isbn = 978-3-540-23025-0| citeseerx=10.1.1.102.4612}}</ref> देखना {{slink|प्रसूची वरण|रूपांतर}} विषय के लिए होता है।
-== के-वे मर्जिंग ==
+== के-वे विलीनीकरण ==
-{{Main|K-way merge algorithm}}
+{{Main|k-वे विलय एल्गोरिथम}}
-{{mvar|k}}-वे मर्जिंग बाइनरी मर्जिंग को मनमाना संख्या में सामान्यीकृत करता है {{mvar|k}} क्रमबद्ध इनपुट सूचियों की। के आवेदन {{mvar|k}}-वे मर्जिंग विभिन्न सॉर्टिंग एल्गोरिदम में उत्पन्न होती है, जिसमें धैर्य सॉर्टिंग भी शामिल है<ref name="Chandramouli">{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014}}</ref> और एक [[बाहरी छँटाई]] एल्गोरिथ्म जो इसके इनपुट को विभाजित करता है {{math|''k'' {{=}} {{sfrac|1|''M''}} − 1}} ब्लॉक जो मेमोरी में फिट होते हैं, इन्हें एक-एक करके सॉर्ट करते हैं, फिर इन ब्लॉक्स को मर्ज कर देते हैं।{{r|toolbox}}{{rp|119–120}}
+{{mvar|k}}-वे विलीनीकरण बाइनरी विलीनीकरण को मनमाना संख्या में सामान्यीकृत करता है, {{mvar|k}} क्रमबद्ध इनपुट सूचियों के आवेदन {{mvar|k}}-वे विलीनीकरण विभिन्न वर्गीकृत एल्गोरिदम में उत्पन्न होती है, जिसमें धैर्य वर्गीकृत भी सम्मिलित है<ref name="Chandramouli">{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014}}</ref> एवं बाहरी वर्गीकृत एल्गोरिथ्म जो इसके इनपुट  {{math|''k'' {{=}} {{sfrac|1|''M''}} − 1}} को विभाजित करता है, इन्हें चयनित करते हैं, इन ब्लॉक्स को विलय कर देते हैं।{{r|toolbox}}{{rp|119–120}}
-इस समस्या के कई समाधान मौजूद हैं। एक भोली समाधान के ऊपर एक लूप करना है {{mvar|k}} प्रत्येक बार न्यूनतम तत्व चुनने के लिए सूचीबद्ध करता है, और इस लूप को तब तक दोहराता है जब तक कि सभी सूचियां खाली न हो जाएं:
+इस समस्या के कई समाधान उपस्थित हैं। समाधान के ऊपर {{mvar|k}} लूप करना है, प्रत्येक बार न्यूनतम तत्व के चयन के लिए सूचीबद्ध करता है, एवं इस लूप को तब तक दोहराता है जब तक कि सभी सूचियां रिक्त न हो जाएं।
-<div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >
+<div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >{{framebox|blue}}
-{{framebox|blue}}
+* इनपुट: की सूची {{mvar|k}} सूचियाँ होती है।
-* इनपुट: की एक सूची {{mvar|k}} सूचियाँ।
+* जबकि कोई भी सूची रिक्त नहीं है।
-* जबकि कोई भी सूची खाली नहीं है:
+** न्यूनतम प्रथम तत्व वाले का शोधन करने के लिए सूचियों पर लूप करें।
-** न्यूनतम पहले तत्व वाले को खोजने के लिए सूचियों पर लूप करें।
+** न्यूनतम तत्व को आउटपुट करें और इसे उसकी सूची से विस्थापित कर दें।
-** न्यूनतम तत्व को आउटपुट करें और इसे उसकी सूची से हटा दें।
 {{frame-footer}}
 </div>
-सबसे अच्छा, सबसे खराब और औसत मामला, यह एल्गोरिथ्म प्रदर्शन करता है {{math|(''k''−1)(''n''−{{sfrac|''k''|2}})}}तत्वों की तुलना अपने कार्य को करने के लिए की जाती है तो कुल मिलाकर {{mvar|n}} सूचियों में तत्व।<ref name="greene">{{cite conference |last=Greene |first=William A. |year=1993 |title=के-वे मर्जिंग और के-आरी सॉर्ट|conference=Proc. 31-st Annual ACM Southeast Conf |pages=127–135 |url=http://www.cs.uno.edu/people/faculty/bill/k-way-merge-n-sort-ACM-SE-Regl-1993.pdf}}</ref>
+सबसे उत्तम, सबसे निकृष्ट एवं औसत विषय {{math|(''k''−1)(''n''−{{sfrac|''k''|2}})}} यह एल्गोरिथ्म प्रदर्शन करता है, तत्वों की तुलना स्वयं कार्य को करने के लिए की जाती है तो कुल मिलाकर {{mvar|n}} सूचियों में तत्व<ref name="greene">{{cite conference |last=Greene |first=William A. |year=1993 |title=के-वे मर्जिंग और के-आरी सॉर्ट|conference=Proc. 31-st Annual ACM Southeast Conf |pages=127–135 |url=http://www.cs.uno.edu/people/faculty/bill/k-way-merge-n-sort-ACM-SE-Regl-1993.pdf}}</ref> को [[प्राथमिकता कतार]] [[ढेर (डेटा संरचना)|(डेटा संरचना)]] में उनके प्रथम तत्व द्वारा कुंजीबद्ध करके इसे सही किया जा सकता है।
-सूचियों को [[प्राथमिकता कतार]] ([[ढेर (डेटा संरचना)]] | न्यूनतम-ढेर) में उनके पहले तत्व द्वारा कुंजीबद्ध करके इसे सुधारा जा सकता है:
 <div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >
 {{framebox|blue}}
-* मिनी-हीप बनाएं {{mvar|h}} की {{mvar|k}} कुंजी के रूप में पहले तत्व का उपयोग करते हुए सूचीबद्ध करता है।
+* कुंजी के रूप में{{mvar|}} प्रथम {{mvar|k}}  तत्व का उपयोग करके k सूचियों का न्यूनतम-सूचीबद्ध h बनाएँ।
-* जबकि कोई भी सूची खाली नहीं है:
+* जबकि कोई भी सूची रिक्त नहीं है।
 ** होने देना {{math|''i'' {{=}} find-min(''h'')}}.
-** सूची का पहला तत्व आउटपुट करें {{mvar|i}} और इसे इसकी सूची से हटा दें।
+** सूची का प्रथम तत्व आउटपुट करें {{mvar|i}} एवं इसे इसको सूची से विस्थापित कर दें।
-** पुनः ढेर करें {{mvar|h}}.
+** पुनः h सूचीबद्ध {{mvar|करें}}.
 {{frame-footer}}
 </div>
-आउटपुट (फाइंड-मिन) होने के लिए अगले सबसे छोटे तत्व की खोज करना और हीप ऑर्डर को पुनर्स्थापित करना अब में किया जा सकता है {{math|''O''(log ''k'')}} समय (अधिक विशेष रूप से, {{math|2⌊log ''k''⌋}} तुलना{{r|greene}}), और पूरी समस्या को हल किया जा सकता है {{math|''O''(''n'' log ''k'')}} समय (लगभग {{math|2''n''⌊log ''k''⌋}} तुलना)।{{r|greene}}<ref name="toolbox">{{cite book|author1=Kurt Mehlhorn|author-link=Kurt Mehlhorn|author2=Peter Sanders|author2-link=Peter Sanders (computer scientist)|title=Algorithms and Data Structures: The Basic Toolbox |date=2008 |publisher=Springer |isbn=978-3-540-77978-0 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/}}</ref>{{rp|119–120}}
+आउटपुट होने के लिए आगामी सबसे अल्प तत्व का शो करना एवं हीप ऑर्डर को पुनर्स्थापित करना {{math|''O''(log ''k'')}} में किया जा सकता है,{{r|greene}} एवं पूर्ण  समस्या का समाधान किया जा सकता है।{{r|greene}}<ref name="toolbox">{{cite book|author1=Kurt Mehlhorn|author-link=Kurt Mehlhorn|author2=Peter Sanders|author2-link=Peter Sanders (computer scientist)|title=Algorithms and Data Structures: The Basic Toolbox |date=2008 |publisher=Springer |isbn=978-3-540-77978-0 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/}}</ref>{{rp|119–120}}
-समस्या के लिए एक तीसरा एल्गोरिथम एक विभाजन और जीत एल्गोरिथम समाधान है जो बाइनरी मर्ज एल्गोरिथम पर बनाता है:
+समस्या के लिए तीसरा एल्गोरिथम विभाजन एवं जीत एल्गोरिथम समाधान है जो बाइनरी मर्ज एल्गोरिथम पर बनाता है।
 <div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >
 {{framebox|blue}}
-* अगर {{math|''k'' {{=}} 1}}, एकल इनपुट सूची का उत्पादन करें।
+* यदि {{math|''k'' {{=}} 1}}, एकल इनपुट सूची का उत्पादन करें।
-* अगर {{math|''k'' {{=}} 2}}, बाइनरी मर्ज करें।
+* यदि {{math|''k'' {{=}} 2}}, बाइनरी मर्ज करें।
-* अन्यथा, पुनरावर्ती रूप से पहले मर्ज करें {{math|⌊''k''/2⌋}} सूचियाँ और अंतिम {{math|⌈''k''/2⌉}} सूचियाँ, फिर बाइनरी इन्हें मर्ज करें।
+* अन्यथा, पुनरावर्ती रूप से पूर्व मर्ज करें {{math|⌊''k''/2⌋}} सूचियाँ एवं अंतिम {{math|⌈''k''/2⌉}} सूचियाँ, बाइनरी इन्हें मर्ज करें।
 {{frame-footer}}
 </div>
-जब इस एल्गोरिथम की इनपुट सूचियों को लंबाई के अनुसार क्रमबद्ध किया जाता है, तो सबसे पहले, इसके लिए इससे कम की आवश्यकता होती है {{math|''n''⌈log ''k''⌉}} तुलना, यानी ढेर-आधारित एल्गोरिथम द्वारा उपयोग की जाने वाली संख्या के आधे से भी कम; व्यवहार में, यह ढेर-आधारित एल्गोरिथम जितना तेज़ या धीमा हो सकता है।{{r|greene}}
+जब इस एल्गोरिथम की इनपुट सूचियों को लंबाई के अनुसार क्रमबद्ध किया जाता है, तो सर्वप्रथम, इसके लिए इससे अर्घ्य की आवश्यकता होती है, {{math|''n''⌈log ''k''⌉}} तुलना अर्थात सूचीबद्ध आधारित एल्गोरिथम द्वारा उपयोग की जाने वाली संख्या के अर्ध से भी अर्घ्य व्यवहार में, यह सूचीबद्ध-आधारित एल्गोरिथम जितना तीव्र या मंद हो सकता है।{{r|greene}}
 == समानांतर विलय ==
-बाइनरी मर्ज एल्गोरिथम का एक [[कार्य समानता]] संस्करण मर्ज सॉर्ट # समानांतर मर्ज सॉर्ट के बिल्डिंग ब्लॉक के रूप में काम कर सकता है। निम्नलिखित स्यूडोकोड इस एल्गोरिथम को एक फोर्क-जॉइन मॉडल में प्रदर्शित करता है। समानांतर विभाजन और जीत शैली (कॉर्मेन एट अल।<ref name="clrs">{{Introduction to Algorithms|3}}</ref>{{rp|800}}). यह दो क्रमबद्ध सरणियों पर काम करता है {{mvar|A}} और {{mvar|B}} और क्रमबद्ध आउटपुट को सरणी में लिखता है {{mvar|C}}. अंकन {{mono|A[i...j]}} का हिस्सा दर्शाता है {{mvar|A}} इंडेक्स से {{mvar|i}} द्वारा {{mvar|j}}, अनन्य।
+बाइनरी मर्ज एल्गोरिथम का [[कार्य समानता]] संस्करण प्रसूची वरण समानांतर प्रसूची वरण के बिल्डिंग ब्लॉक के रूप में कार्य कर सकता है। निम्नलिखित स्यूडोकोड इस एल्गोरिथम को फोर्क-जॉइन मॉडल में प्रदर्शित करता है। समानांतर विभाजन एवं जीत शैली<ref name="clrs">{{Introduction to Algorithms|3}}</ref>{{rp|800}} यह दो क्रमबद्ध सारणीयो पर कार्य करता है, {{mvar|A}} एवं {{mvar|B}} क्रमबद्ध आउटपुट को सारणी में लिखता है, {{mvar|C}}. अंकन {{mono|A[i...j]}} का भाग दर्शाता है।
-  एल्गोरिदम मर्ज (ए[आई...जे], बी[के...ℓ], सी[पी...क्यू]) है
+  '''algorithm''' merge(A[i...j], B[k...ℓ], C[p...q]) '''is'''
-      इनपुट ए, बी, सी: सरणी
+      '''inputs''' A, B, C : array
-             i, j, k, ℓ, p, q : सूचकांक
+             i, j, k, ℓ, p, q : indices
-      चलो एम = जे - मैं,
+      '''let''' m = j - i,
-          एन = ℓ - के
+          n = ℓ - k
-      अगर एम <एन तो
+      '''if''' m < n '''then'''
-          स्वैप ए और बी '' // सुनिश्चित करें कि ए बड़ा सरणी है: i, j अभी भी A से संबंधित है; k, ℓ से B''
+          swap A and B  ''// ensure that A is the larger array: i, j still belong to A; k, ℓ to B''
-          एम और एन स्वैप करें
+          swap m and n
-      अगर एम ≤ 0 तो
+      '''if''' m ≤ 0 '''then'''
-          रिटर्न ''// बेस केस, मर्ज करने के लिए कुछ नहीं''
+          '''return'''  ''// base case, nothing to merge''
-      चलो आर = ⌊(i + j)/2⌋
+      '''let''' r = ⌊(i + j)/2⌋
-      चलो एस = बाइनरी-सर्च (ए [आर], बी [के ... ℓ])
+      '''let''' s = binary-search(A[r], B[k...ℓ])
-      माना टी = पी + (आर - आई) + (एस - के)
+      '''let''' t = p + (r - i) + (s - k)
-      सी [टी] = ए [आर]
+      C[t] = A[r]
-      समानांतर करते हैं
+      '''in parallel do'''
-          मर्ज (ए[आईआर...आर], बी[के...एस], सी[पी...टी])
+          merge(A[i...r], B[k...s], C[p...t])
-         विलय (ए [आर + 1 ... जे], बी [एस ... ℓ], सी [टी + 1 ... क्यू])
-एल्गोरिथ्म या तो विभाजित करके संचालित होता है {{mvar|A}} या {{mvar|B}}, जो भी बड़ा हो, (लगभग) बराबर हिस्सों में। इसके बाद यह दूसरे सरणी को पहले के मध्य बिंदु से छोटे मान वाले भाग में और बड़े या समान मान वाले भाग में विभाजित करता है। ([[द्विआधारी खोज]] उपनेमका सूचकांक को अंदर लौटाता है {{mvar|B}} कहाँ {{math|''A''[''r'']}} होगा, अगर यह अंदर होता {{mvar|B}}; कि यह हमेशा के बीच एक संख्या है {{mvar|k}} और {{mvar|ℓ}}।) अंत में, हिस्सों की प्रत्येक जोड़ी विलय कर दी जाती है और एल्गोरिदम जीतते हैं, और चूंकि रिकर्सिव कॉल एक दूसरे से स्वतंत्र होते हैं, इसलिए उन्हें समानांतर में किया जा सकता है। हाइब्रिड दृष्टिकोण, जहां रिकर्सन बेस केस के लिए सीरियल एल्गोरिदम का उपयोग किया जाता है, अभ्यास में अच्छा प्रदर्शन करने के लिए दिखाया गया है <ref name="vjd">{{citation| author=Victor J. Duvanenko| title=Parallel Merge| journal=Dr. Dobb's Journal| date=2011| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>
+ merge(A[r+1...j], B[s...ℓ], C[t+1...q])
-समांतर एल्गोरिदम का विश्लेषण # एल्गोरिदम द्वारा कुल मिलाकर दो सरणी के लिए किया गया अवलोकन {{mvar|n}} एलिमेंट्स, यानी इसके सीरियल वर्जन का रनिंग टाइम है {{math|''O''(''n'')}}. यह तब से इष्टतम है {{mvar|n}} तत्वों को कॉपी करने की आवश्यकता है {{mvar|C}}. समांतर एल्गोरिदम के विश्लेषण की गणना करने के लिए # एल्गोरिदम का अवलोकन, [[पुनरावृत्ति संबंध]] प्राप्त करना आवश्यक है। चूंकि विलय की दो रिकर्सिव कॉल समानांतर में हैं, केवल दो कॉलों के महंगे होने पर विचार करने की आवश्यकता है। सबसे खराब स्थिति में, एक पुनरावर्ती कॉल में तत्वों की अधिकतम संख्या अधिकतम होती है <math display="inline">\frac 3 4 n</math> चूंकि अधिक तत्वों वाला सरणी आधे में पूरी तरह से विभाजित है। जोड़ना <math>\Theta\left( \log(n)\right)</math> बाइनरी सर्च की लागत, हम इस पुनरावृत्ति को ऊपरी सीमा के रूप में प्राप्त करते हैं:
-<math>T_{\infty}^\text{merge}(n) = T_{\infty}^\text{merge}\left(\frac {3} {4} n\right) + \Theta\left( \log(n)\right)</math>
+एल्गोरिथ्म या तो विभाजित करके संचालित होता है {{mvar|A}} या {{mvar|B}}, जो भी बड़ा हो, (लगभग) समान भागो में इसके पश्चात यह दूसरे सरणी को प्रथम के मध्य बिंदु से अल्प मान वाले भाग में एवं बड़े या समान मान वाले भाग में विभाजित करता है। अंत में, भागो की प्रत्येक जोड़ी विलय कर दी जाती है एवं एल्गोरिदम विजयी होते हैं, एवं चूंकि रिकर्सिव कॉल दूसरे से स्वतंत्र होते हैं, इसलिए उन्हें समानांतर में किया जा सकता है। हाइब्रिड दृष्टिकोण, जहां पुनरावर्तन आधार विषय के लिए सीरियल एल्गोरिदम का उपयोग किया जाता है, अभ्यास में अच्छा प्रदर्शन करने के लिए दिखाया गया है। <ref name="vjd">{{citation| author=Victor J. Duvanenko| title=Parallel Merge| journal=Dr. Dobb's Journal| date=2011| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref> समांतर एल्गोरिदम का विश्लेषण एल्गोरिदम द्वारा कुल मिलाकर दो सारणी के लिए किया गया अवलोकन {{mvar|n}} एलिमेंट्स, अर्थात {{math|''O''(''n'')}} इसके सीरियल वर्जन का रनिंग टाइम है, यह तब से इष्टतम है {{mvar|n}} तत्वों को कॉपी करने की आवश्यकता है {{mvar|C}}. समांतर एल्गोरिदम के विश्लेषण की गणना करने के लिए एल्गोरिदम का अवलोकन, [[पुनरावृत्ति संबंध]] प्राप्त करना आवश्यक है। चूंकि विलय की दो रिकर्सिव कॉल समानांतर में हैं, केवल दो कॉलों के मूल्यवान होने पर विचार करने की आवश्यकता है। सबसे निकृष्ट स्थिति में, पुनरावर्ती कॉल में तत्वों की अधिकतम संख्या <math display="inline">\frac 3 4 n</math> अधिकतम होती है, चूंकि अधिक तत्वों वाला सरणी अर्ध में पूर्ण रूप से विभाजित है। <math>\Theta\left( \log(n)\right)</math> जोड़ना बाइनरी सर्च की वित्त, इस पुनरावृत्ति को ऊपरी सीमा के रूप में प्राप्त करते हैं।
-समाधान है <math>T_{\infty}^\text{merge}(n) = \Theta\left(\log(n)^2\right)</math>, जिसका अर्थ है कि एक आदर्श मशीन पर असीमित संख्या में प्रोसेसर के साथ इतना समय लगता है।{{r|clrs}}{{rp|801–802}}
-नोट: रूटीन छँटाई एल्गोरिथ्म नहीं है # स्थिरता: यदि समान आइटम विभाजित करके अलग किए जाते हैं {{mvar|A}} और {{mvar|B}}, वे इसमें इंटरलीव हो जाएंगे {{mvar|C}}; अदला-बदली भी {{mvar|A}} और {{mvar|B}} ऑर्डर को नष्ट कर देगा, यदि दोनों इनपुट सरणियों के बीच समान आइटम फैले हुए हैं। परिणामस्वरूप, जब छँटाई के लिए उपयोग किया जाता है, तो यह एल्गोरिथम एक ऐसा क्रम उत्पन्न करता है जो स्थिर नहीं होता है।
+समाधान <math>T_{\infty}^\text{merge}(n) = T_{\infty}^\text{merge}\left(\frac {3} {4} n\right) + \Theta\left( \log(n)\right)</math> है,  <math>T_{\infty}^\text{merge}(n) = \Theta\left(\log(n)^2\right)</math>, जिसका अर्थ है कि आदर्श मशीन पर असीमित संख्या में प्रोसेसर के साथ इतना समय लगता है।{{r|clrs}}{{rp|801–802}}
+{{mvar|A}} एवं {{mvar|B}}, वे इसमें इंटरलीव हो जाएंगे {{mvar|C}}; परिवर्तन भी {{mvar|A}} एवं {{mvar|B}} ऑर्डर को नष्ट कर देगा, यदि दोनों इनपुट सरणियों के मध्य समान आइटम विस्तृत हुए हैं। परिणामस्वरूप, जब विलय के लिए उपयोग किया जाता है, तो यह एल्गोरिथम ऐसा क्रम उत्पन्न करता है जो स्थिर नहीं होता है।
 == दो सूचियों का समानांतर विलय ==
@@ Line 123: / Line 119: @@
 ऐसे एल्गोरिदम भी हैं जो दो क्रमबद्ध सूचियों के विलय के एक उदाहरण के भीतर समानता का परिचय देते हैं। इनका उपयोग फील्ड-प्रोग्रामेबल गेट एरेज़ ([[FPGA]]s), विशेष सॉर्टिंग सर्किट के साथ-साथ आधुनिक प्रोसेसर में सिंगल-इंस्ट्रक्शन मल्टीपल-डेटा ([[SIMD]]) निर्देशों के साथ किया जा सकता है।
-मौजूदा समानांतर एल्गोरिदम या तो [[बिटोनिक सॉर्टर]] या [[सम-विषम मर्ज सॉर्ट]] के मर्ज भाग के संशोधनों पर आधारित हैं।<ref name="flimsj">{{cite journal |last1=Papaphilippou |first1=Philippos |last2=Luk |first2=Wayne |last3=Brooks |first3=Chris |title=FLiMS: a Fast Lightweight 2-way Merger for Sorting |journal=IEEE Transactions on Computers |date=2022 |pages=1–12 |doi=10.1109/TC.2022.3146509|hdl=10044/1/95271 |hdl-access=free }}</ref> 2018 में, सैतोह एम। एट अल। एमएमएस पेश किया <ref>{{cite journal |last1=Saitoh |first1=Makoto |last2=Elsayed |first2=Elsayed A. |last3=Chu |first3=Thiem Van |last4=Mashimo |first4=Susumu |last5=Kise |first5=Kenji |title=फीडबैक डेटापथ के बिना एक उच्च-प्रदर्शन और लागत प्रभावी हार्डवेयर मर्ज सॉर्टर|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) |date=April 2018 |pages=197–204 |doi=10.1109/FCCM.2018.00038}}</ref> FPGAs के लिए, जो एक बहु-चक्र फीडबैक डेटापथ को हटाने पर केंद्रित था जो हार्डवेयर में कुशल पाइपलाइनिंग को रोकता था। इसके अलावा 2018 में, Papaphilippou P. et al। FLiMS पेश किया <ref name="flimsj" />जिसने केवल आवश्यकता के द्वारा हार्डवेयर उपयोग और प्रदर्शन में सुधार किया <math>\log_2(P)+1</math> के पाइपलाइन चरण {{math|''P/2''}} की समानता के साथ विलय करने के लिए इकाइयों की तुलना और अदला-बदली करें {{math|''P''}} एफपीजीए चक्र प्रति तत्व।
+उपस्थिता समानांतर एल्गोरिदम या तो [[बिटोनिक सॉर्टर]] या [[सम-विषम मर्ज सॉर्ट|सम-विषम विलय]] के भाग के संशोधनों पर आधारित हैं।<ref name="flimsj">{{cite journal |last1=Papaphilippou |first1=Philippos |last2=Luk |first2=Wayne |last3=Brooks |first3=Chris |title=FLiMS: a Fast Lightweight 2-way Merger for Sorting |journal=IEEE Transactions on Computers |date=2022 |pages=1–12 |doi=10.1109/TC.2022.3146509|hdl=10044/1/95271 |hdl-access=free }}</ref> <ref>{{cite journal |last1=Saitoh |first1=Makoto |last2=Elsayed |first2=Elsayed A. |last3=Chu |first3=Thiem Van |last4=Mashimo |first4=Susumu |last5=Kise |first5=Kenji |title=फीडबैक डेटापथ के बिना एक उच्च-प्रदर्शन और लागत प्रभावी हार्डवेयर मर्ज सॉर्टर|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) |date=April 2018 |pages=197–204 |doi=10.1109/FCCM.2018.00038}}</ref> FPGAs के लिए, जो बहु-चक्र प्रतिक्रिया डेटापथ को विस्थापित करने पर केंद्रित था जो हार्डवेयर में कुशल पाइपलाइनिंग को रोकता था। इसके अतिरिक्त 2018 में, Papaphilippou P. et al। FLiMS प्रस्तुत की गयी <ref name="flimsj" />जिसने केवल आवश्यकता के द्वारा हार्डवेयर उपयोग एवं प्रदर्शन में सुधार किया <math>\log_2(P)+1</math> के पाइपलाइन चरण {{math|''P/2''}} की समानता के साथ विलय करने के लिए इकाइयों की तुलना एवं {{math|''P''}}  FPGA  चक्र प्रति तत्व परिवर्तन किया।
 == भाषा समर्थन ==
-कुछ [[कंप्यूटर भाषा]]एँ सॉर्ट किए गए [[संग्रह (सार डेटा प्रकार)]] को मर्ज करने के लिए अंतर्निहित या लाइब्रेरी समर्थन प्रदान करती हैं।
+कुछ कंप्यूटर भाषाएँ सॉर्ट किए गए [[संग्रह (सार डेटा प्रकार)]] को मर्ज करने के लिए अंतर्निहित या लाइब्रेरी समर्थन प्रदान करती हैं।
-=== [[सी ++]] ===
+=== C ++ ===
-सी ++ की [[मानक टेम्पलेट लाइब्रेरी]] में फ़ंक्शन है {{mono|std::merge}}, जो पुनरावर्तकों की दो क्रमबद्ध श्रेणियों को मिलाता है, और {{mono|std::inplace_merge}}, जो लगातार दो क्रमबद्ध श्रेणियों को इन-प्लेस मर्ज करता है। इसके साथ में {{mono|std::list}} (लिंक की गई सूची) वर्ग का अपना है {{mono|merge}} विधि जो दूसरी सूची को अपने आप में विलीन कर देती है। विलय किए गए तत्वों के प्रकार को इससे कम का समर्थन करना चाहिए ({{mono|<}}) ऑपरेटर, या इसे एक कस्टम तुलनित्र प्रदान किया जाना चाहिए।
+C ++ की मानक टेम्पलेट लाइब्रेरी में {{mono|std::merge}} फ़ंक्शन है, जो पुनरावर्तकों की दो क्रमबद्ध श्रेणियों को मिलाता है, एवं {{mono|std::inplace_merge}}, जो निरंतर दो क्रमबद्ध श्रेणियों को इन-प्लेस मर्ज करता है। इसके साथ में {{mono|std::list}} (लिंक की गई सूची) वर्ग का स्वयं का {{mono|merge}} है, विधि जो दूसरी सूची को स्वयं में विलीन कर देती है। विलय किए गए तत्वों के प्रकार को इससे अर्घ्य का समर्थन करना चाहिए, ({{mono|<}}) ऑपरेटर, या इसे प्रथा तुलनित्र प्रदान किया जाना चाहिए।
-सी ++ 17 अलग-अलग निष्पादन नीतियों की अनुमति देता है, अर्थात् अनुक्रमिक, समांतर, और समांतर-अनुक्रमित।<ref>{{cite web| url=http://en.cppreference.com/w/cpp/algorithm/merge| title=std:merge| publisher=cppreference.com| date=2018-01-08| access-date=2018-04-28}}</ref>
+C ++ 17 भिन्न-भिन्न निष्पादन नीतियों की अनुमति देता है, अर्थात् अनुक्रमिक, समांतर, एवं समांतर-अनुक्रमित होते है।<ref>{{cite web| url=http://en.cppreference.com/w/cpp/algorithm/merge| title=std:merge| publisher=cppreference.com| date=2018-01-08| access-date=2018-04-28}}</ref>
 === पायथन ===
-पायथन (प्रोग्रामिंग लैंग्वेज) की मानक लाइब्रेरी (2.6 के बाद से) में भी a {{mono|merge}} में कार्य करता है {{mono|heapq}} मॉड्यूल, जो कई क्रमबद्ध पुनरावृत्तियों को लेता है, और उन्हें एक एकल पुनरावर्तक में मिला देता है।<ref>{{cite web| url = https://docs.python.org/library/heapq.html#heapq.merge| title = heapq — Heap queue algorithm — Python 3.10.1 documentation}}</ref>
+पायथन (प्रोग्रामिंग लैंग्वेज) की मानक लाइब्रेरी (2.6 के पश्चात से) में भी a {{mono|merge}} में कार्य करता है {{mono|heapq}} मॉड्यूल, जो कई क्रमबद्ध पुनरावृत्तियों को लेता है, एवं उन्हें एकल पुनरावर्तक में मिला देता है।<ref>{{cite web| url = https://docs.python.org/library/heapq.html#heapq.merge| title = heapq — Heap queue algorithm — Python 3.10.1 documentation}}</ref>
@@ Line 156: / Line 152: @@
 *[https://duvanenko.tech.blog/2018/05/23/faster-sorting-in-c/ High Performance Implementation] of Parallel and Serial Merge in [[C Sharp (programming language)|C#]] with source in [https://github.com/DragonSpit/HPCsharp/ GitHub] and in [[C++]] [https://github.com/DragonSpit/ParallelAlgorithms GitHub]
-{{sorting}}
+{{DEFAULTSORT:Merge Algorithm}}
-{{DEFAULTSORT:Merge Algorithm}}[[Category: स्यूडोकोड के उदाहरण वाले लेख]] [[Category: छँटाई एल्गोरिदम]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Merge Algorithm]]
-[[Category:Created On 13/05/2023]]
+[[Category:Created On 13/05/2023|Merge Algorithm]]
+[[Category:Lua-based templates|Merge Algorithm]]
+[[Category:Machine Translated Page|Merge Algorithm]]
+[[Category:Pages with script errors|Merge Algorithm]]
+[[Category:Templates Vigyan Ready|Merge Algorithm]]
+[[Category:Templates that add a tracking category|Merge Algorithm]]
+[[Category:Templates that generate short descriptions|Merge Algorithm]]
+[[Category:Templates using TemplateData|Merge Algorithm]]
+[[Category:छँटाई एल्गोरिदम|Merge Algorithm]]
+[[Category:स्यूडोकोड के उदाहरण वाले लेख|Merge Algorithm]]

Anonymous

Search

मर्ज एल्गोरिथम: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:06, 30 October 2023

Contents

आवेदन

दो सूचियों को विलय करना

के-वे विलीनीकरण

समानांतर विलय

दो सूचियों का समानांतर विलय

भाषा समर्थन

C ++

पायथन

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

मर्ज एल्गोरिथम: Difference between revisions

Latest revision as of 16:06, 30 October 2023

आवेदन

दो सूचियों को विलय करना

के-वे विलीनीकरण

समानांतर विलय

दो सूचियों का समानांतर विलय

भाषा समर्थन

C ++

पायथन

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories