मर्ज एल्गोरिदम

right|thumb|300px| विलय अनुक्रमण का एक उदाहरण। पहले सूची को सबसे छोटी इकाई (1 तत्व) में विभाजित करें, फिर दो आसन्न सूचियों को अनुक्रमित करने और विलय करने के लिए आसन्न सूची के साथ प्रत्येक तत्व की तुलना करें। अंत में सभी तत्वों को क्रमबद्ध और विलय कर दिया जाता है। कम्प्यूटर विज्ञान मे उन कलनविधियों को अनुक्रमण कलनविधि कहते हैं जो किसी सूची के मूल क्रम बदलकर किसी अन्य क्रम विशेष सूची मे बदलने के काम आता है। इनमें से प्रसिद्ध अनुक्रमण कलनविधि है विलय अनुक्रमण। यह तुलना पर आधारित अनुक्रमण विधि है। विलय अनुक्रमण विभाजन और जीत की विधि पर आधारित है जिसकी खोज जॉन वाॅन न्यूमन ने सन् १९४५ में की थी Donald Knuth Donald Knuth The Art of Computer Programming 3: Sorting and Searching 2nd Addison-Wesley 1998 978-0-201-89685-5 513–558 । विलय अनुक्रमण एक स्थिर अनुक्रमण कलनविधि भी है, जिसमे बराबर वस्तुओं का क्रम नहीं बदलता। इसका विस्तृत विवरण गोल्डस्टीन और न्यूमन की रिपोर्ट मे सामने आयी जो सन् १९४८ में प्रकाशित हुई। अल्गोरिथम विलय अनुक्रमण की संकल्पना कुछ इस प्रकार से किया जा सकता है : १) एक अनसुलझी सूची जिसमे n संख्या/वस्तु है। २) अनसुलझी सूची को n उपसूची मे विभाजित करेंगे, जिसमे हर उपसूची मे एक संख्या होगी। ३) बार-बार उपसूची को विलय/मिलाव करके नई सुलझी हुई उपसूची बनाते रहेंगे जब तक एक उपसूची नहीं बच जाती। कार्यान्वयन right|thumb|300px| विलय अनुक्रमण का एक उदाहरण। एक सामान्य विलय अनुक्रमण विधि नीचे से ऊपर के दृष्टिकोण आधारित है। मान लीजिये की एक अनसुलझी सूची ३८ २७ ४३ ३ ९ ८२ १० दी गयी है। इसे सुलझाने के लिए निम्न प्रक्रिया अपनाएंगे : १) इन संख्याओं को दो उपसूची मे विभाजित करना है। २) पुनः दो उपसूची को चार उपसूची मे विभाजित करेंगे। ३) फिर इन चार उपसूची को तोड़ने मे सात उपसूची मिल जाएगी जिनमें हर उपसूची मे सिर्फ एक संख्या होगी । ४) अब जिस प्रकार से उपसूची तोड़ी उसी प्रकार से उपसूची जोड़ेंगे इस बात को ध्यान रखते हुए की नई उपसूची हमेशा सुलझी हुई हो। अब हमें वापस चार सुलझी हुई उपसूची मिलेगी। ५) अब इन चार उपसूची को जोड़ेंगे जिससे दो सुलझी हुई उपसूची मिल जाएगी। ६) अंत मे इन दो सुलझी हुई उपसूची को मिला के एक नई उपसूची बनेगी जो अनुक्रमित होगी। उदाहरण सूची को हर चरण के बाद कुछ इस तरह से देखा जा सकता : (३८ २७ ४३ ३ ९ ८२ १०)-> (३८ २७ ४३ ३ ),(९ ८२ १० )-> (३८ २७),(४३ ३ ),(९ ८२ ),(१०)-> (३८),(२७),(४३),(३),(९),(८२),(१०)-> (२७ ३८),(३ ४३),(९ ८२),(१०)-> (३ २७ ३८ ४३),(९ १० ८२)-> (३ ९ १० २७ ३८ ४३ ८२) इसको समझने के लिए दिए गए चित्र का उपयोग कर सकते है। विश्लेषण विलय अनुक्रमण एक स्थिर अनुक्रमण विधि है जिसमे समान संख्या का क्रम नहीं बदलता है संख्या को सुलझाने मे विलय अनुक्रमण का औसत समय और सबसे ख़राब समय की जटिलता O(nlgn) है। अगर n संख्या को कार्य पूरा करने मे t(n) समय लगता है तो T(n) = 2T(n/2) + n जो विलय अनुक्रमण के परिभाषा से पता चलता है Cormen Thomas H. Thomas H. Cormen Leiserson Charles E. Charles E. Leiserson Rivest Ronald L. Ronald L. Rivest Stein Clifford Clifford Stein Introduction to Algorithms 3rd Massachusetts Institute of Technology 2009 978-0-262-03384-8 253–280 Introduction to Algorithms । यहाँ 2T(n/2) यह विधि दोबारा दो हिस्सों मे लगाई जाने से आता है और n उन दो उपसूची को जोड़ने का समय बयान करता है। इस पुनरावृत्ति को मास्टर्स थ्योरम के इस्तमाल से हल किया जा सकता है। मास्टर्स थ्योरम T(n) जो की समय की जटिलता है वो O(nlgn) देता है। समय के बाद अगर जगह की जटिलता देखे तो वह O(n) है। यह जगह दो उपसूची को जोड़ने के वक़्त इस्तेमाल होती है। अगर हमे इसे नयी जगह देने से रोकना है और O(1) जगह जटिलता में करना है तो विलय अनुक्रमण की समय जटिलता O (n*n) हो जाएगी। हालांकि एक तरीका है जिसमे समय O(nlgn) और जगह O(1) होगी। इसमे सूची के एक स्थान में दो संख्या रखने की जरुरत होगी जो डिवीज़न अल्गोरिथम के मदद से हल किया जा सकता है। Skiena Steven S. Steven Skiena The Algorithm Design Manual https://archive.org/details/algorithmdesignm00skie_772 2nd Springer 2008 4.5: Mergesort: Sorting by Divide-and-Conquer 120–125 978-1-84800-069-8 सन्दर्भ