डेटा संरचना में एल्गोरिदम मर्ज करें

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

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

आइए बेहतर विचार प्राप्त करने के लिए दृष्टांत देखें।

एल्गोरिदम

मर्ज करें (सरणी, बाएँ, मध्य, दाएँ) −

Begin
   nLeft := m - left+1
   nRight := right – m
   define arrays leftArr and rightArr of size nLeft and nRight respectively
   for i := 0 to nLeft do
      leftArr[i] := array[left +1]
   done
   for j := 0 to nRight do
      rightArr[j] := array[middle + j +1]
   done
   i := 0, j := 0, k := left
   while i < nLeft AND j < nRight do
      if leftArr[i] <= rightArr[j] then
         array[k] = leftArr[i]
         i := i+1
      else
         array[k] = rightArr[j]
         j := j+1
         k := k+1
      done
   while i < nLeft do
      array[k] := leftArr[i]
      i := i+1
      k := k+1
   done
   while j < nRight do
      array[k] := rightArr[j]
      j := j+1
      k := k+1
   done
End