मर्ज एल्गोरिदम का उपयोग दो क्रमबद्ध सूचियों को एक सूची में मर्ज करने के लिए किया जाता है। इस एल्गोरिदम का उपयोग विभिन्न मामलों में किया जाता है। यदि हम मर्ज सॉर्ट करना चाहते हैं, तो हमें क्रमबद्ध सूचियों को बड़ी सूचियों में मर्ज करने की आवश्यकता होती है।
दृष्टिकोण सरल है। हम दो सूचियाँ लेते हैं, दो पॉइंटर्स होंगे। पहला पहली सूची के तत्व की ओर इंगित करेगा, दूसरा दूसरी सूची के तत्वों की ओर इंगित करेगा। उनके मूल्यों के आधार पर, छोटे तत्व को इन दो सूचियों में से एक से लिया जाता है, फिर उस संबंधित सूची का पॉइंटर बढ़ाया जाता है। यह संक्रिया तब तक की जाएगी जब तक एक सूची समाप्त नहीं हो जाती। उसके बाद शेष सूची को अंतिम मर्ज की गई सूची के अंत में जोड़ दिया जाता है।
बेहतर विचार पाने के लिए चित्र देखें।
एल्गोरिदम
Merge(array, left, middle, right) –
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
