মডিউল ২৩_১ঃ Merge Two Sorted Arrays

আমরা সর্ট করার আগে দুইটা সর্টেড এ্যারেকে কিভাবে merge করা যায় সেটা নিয়ে চিন্তা করি।

ধরি,

দুইটা এ্যারে আছে সর্টেড। এবার এদেরকে merge করে নতুন এ্যারে বানাইতে হবে। তাহলে সেটা কিভাবে করা যায়।

এই ক্ষেত্রে আমরা প্রথমে ফার্স্ট এ্যারে এর সমান করে L একটি এ্যারে বানাবো ও ফার্স্ট এ্যারেকে সেই L এ কপি করবো। সেইম ভাবে সেকেন্ড এ্যারে এর জন্য R একটি এ্যারে বানাবো তারপর সেই সেকেন্ড এ্যারেকে R এ কপি করবো।

এবার দুইটা পয়েন্টার সেট করবো। একটা পয়েন্টা i L এ্যারে এর ফার্স্ট ইন্ডেক্সে আরেকটা পয়েন্টার j R এ্যারে এর ফার্স্ট ইন্ডেক্সে সেট করবো। আর একটা এ্যারে নিবো L+R সাইজের যেখানে merge করা এ্যারেটা থাকবে।

এবার i তম এলিমেন্ট এর সাথে j তম এলিমেন্টকে কম্পেয়ার করবো। যদি i তম এলিমেন্ট ছোট হয় তাহলে আন্সার এ্যারেতে i তম এলিমেন্ট বসিয়ে দিবো আর i এর ভ্যালু ১ করে বাড়িয়ে দিবো। আর যদি j তম এলিমেন্ট ছোট হয় তাহলে j এর ভ্যালু আন্সার এ্যারেতে বসিয়ে দিবো আর j এর ভ্যালু ১ করে বাড়িয়ে দেবো।

উদাহরণ হিসেবে,

প্রথমে i = 0, j = 0

L[i]< R[j]

তাই, ans[0] = L[i]

i++[i = 1]

এভাবে পুরো প্রসেসটা আগাতে থাকবে ও শেষ অব্দি ফাইনাল এ্যারেটি হবে