মার্জ সর্ট সম্পর্কে আলোচনা

যেহেতু আমরা বিভক্তি এবং জয়(ডিভাইড অ্যান্ড কনকার) পদ্ধতি ব্যবহার করে সাজাবো, আমাদের ঠিক করে নিতে হবে ছোট সমস্যাগুলো কেমন হবে। সম্পূর্ণ সমস্যাটি হল একটি পুরো অ্যারেকে সাজানো। ধরি ছোট সমস্যা হবে সাবঅ্যারেকে সাজানো। বিশেষ করে, আমরা ছোট সমস্যাটাকে এভাবে চিন্তা করব, একটি সাবঅ্যারের $p$‍ থেকে $r$‍ পর্যন্ত উপাদানগুলো সাজাতে হবে। সাবঅ্যারের জন্য একটি চিহ্ন ব্যবহার করলে ভালো হয়, তো আমরা বলতে পারি array[p..r] হল ওই অ্যারের সাবঅ্যারে। লক্ষ্য কর এই "দুই-ডট" চিহ্ন প্রকৃত জাভাস্ক্রিপ্ট নয়; আমরা এটা শুধু অ্যালগোরিদম বর্ণনা করার জন্য ব্যবহার করব, অ্যালগোরিদমকে কোড আকারে প্রকাশ করার জন্য নয়। আমাদের চিহ্নের সাপেক্ষে, $n$‍ উপাদান বিশিষ্ট একটি অ্যারের জন্য, আমরা বলতে পারি মূল সমস্যাটি হল array[0..n-1] কে সাজানো।

মার্জসর্ট যেভাবে বিভক্তি এবং জয় পদ্ধতি ব্যবহার করে:

আমাদের একটি বেস কেস দরকার। বেস কেস হল একটি সাবঅ্যারে যার উপাদান দুইয়ের কম, এটা হয় যখন $p\ge r$‍, কারণ কোন সাবঅ্যারে যার একটি উপাদান আছে বা কোন উপাদান নেই সেটা সাজানোই আছে। তাহলে আমরা বিভক্তকরন-জয়-একত্রকরণ করব শুধুমাত্র যখন $p<r$‍।

চল একটি উদাহরণ দেখি। ধরি একটি অ্যারেতে আছে [14, 7, 3, 12, 9, 11, 6, 2], তো প্রথম সাবঅ্যারেটি হবে সম্পূর্ণ অ্যারে, array[0..7] ($p=0$‍ and $r=7$‍)। এই সাবঅ্যারেতে কমপক্ষে দুইটি উপাদান আছে, আর তাই এটা বেস কেস হবে না।

array[0..3] সাবঅ্যারেটি কীভাবে সাজানো হল? সেই একই উপায়ে। এর দুইয়ের অধিক উপাদান আছে, আর তাই এটা বেস কেস না। এখানে $p=0$‍ এবং $r=3$‍, পেলাম $q=1$‍, array[0..1] বা ([14, 7]) এবং array[2..3] বা ([3, 12]) কে বারবার সাজানো হবে, আমরা পাব array[0..3] যেটাতে আছে [7, 14, 3, 12] এবং প্রথম অর্ধেকের সাথে পরের অর্ধেক মিলিয়ে, পেলাম [3, 7, 12, 14]।

array[0..1] সাবঅ্যারেটি কীভাবে সাজানো হল? এখানে $p=0$‍ এবং $r=1$‍, পেলাম $q=0$‍, array[0..0] যা ([14]) এবং array[1..1] যা ([7]) কে বারবার সাজানো হবে, আমরা পাব array[0..1] যেটাতে থাকবে [14, 7] এবং প্রথম অর্ধেকের সাথে পরের অর্ধেক মিলিয়ে, পেলাম [7, 14]।

array[0..0] এবং array[1..1] সাবঅ্যারে দুইটি হল বেস কেস, যেহেতু প্রত্যেকের দুইয়ের কম উপাদান আছে। এখানে দেখানো হয়েছে কীভাবে মার্জসর্ট অ্যালগোরিদম কাজ করে:

Most of the steps in merge sort are simple. You can check for the base case easily. Finding the midpoint $q$‍ in the divide step is also really easy. You have to make two recursive calls in the conquer step. It's the combine step, where you have to merge two sorted subarrays, where the real work happens.

In the next challenge, you'll focus on implementing the overall merge sort algorithm, to make sure you understand how to divide and conquer recursively. After you've done that, we'll dive deeper into how to merge two sorted subarrays efficiently and you'll implement that in the later challenge.

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।