ডেটা স্ট্রাকচরে মার্জ অ্যালগরিদম

মার্জ অ্যালগরিদম দুটি সোর্টেড লিস্টকে একটি লিস্টে মার্জ করতে ব্যবহৃত হয়। এই অ্যালগরিদম বিভিন্ন কেসে ব্যবহার হয়। যদি আমরা মার্জ সোর্ট করতে চাই, তবে সোর্টেড লিস্টগুলো বড় লিস্টে মার্জ করতে হবে।

অ্যাপ্রোচটি সহজ। আমরা দুটি লিস্ট নেই, দুটি পয়েন্টার থাকবে। প্রথমটি প্রথম লিস্টের উপাদানকে নির্দেশ করবে, দ্বিতীয়টি দ্বিতীয় লিস্টের উপাদানকে। তাদের মান অনুযায়ী, ছোট উপাদানটি দুটি লিস্টের যেকোনো একটি থেকে নেওয়া হবে, তারপর সেই লিস্টের পয়েন্টার বাড়ানো হবে। এই অপারেশনটি तब तक চলবে যতক্ষণ না একটি লিস্ট শেষ হয়। তারপর বাকি লিস্টটি ফাইনাল মার্জড লিস্টের শেষে যোগ করা হবে।

বালগো বুঝতে নিচের ইলাস্ট্রেশন দেখুন।

অ্যালগরিদম

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