ধর,তোমরা কয়েক জন বন্ধু দার্জিলিং ঘুরতে গিয়ে ক্যাটরিনার দেখা পাইলা।কিন্তু তোমাদের সবাই ক্যাট কে চায়ই চায়।ক্যাট ও তোমাদের সবাই কে চায়💚 কারণ তোমরা সবাই অনেক স্মার্ট😂।কিন্তু ক্যাট ভাবল সবাইকে নিলে, ব্যাপারটা কেমন অনৈতিক হয়ে যায়💘 তাই সে তোমাদের একটা প্রস্তাব দিল,কত গুলো নাম্বার কে যে যত কম টাইম কমপ্লেক্সিটি তে সর্ট করতে পারবে,তাকেই সে বফ বানাবে😙। তো তুমি চিন্তা করলে,বাবল সর্ট করলে নিশ্চিত ধরা খাব,তার চেয়ে বরং মার্জ সর্ট মেরে দেয়(কারণ তুমি ল্যাব ভাইভার জন্য মুখস্ত করছিলা🙌 যে মার্জ সর্টের কমপ্লেক্সিটি(worst case: O(N log N)),অন্ততপক্ষে বাবল সর্টের(worst case: O(N^2)) চেয়ে কম)।দেখা যাক,কপালে কি আছে!😰কিন্তু তুমি তো মার্জ সর্টও জানো না।তাইলে চলো শিখে নেই,ক্যাট কে পাবার জন্য হলেও!😍
মার্জ সর্ট হল খুবই কার্যকরী একটি সর্টিং অ্যালগরিদম।এটা Divide and Conquer পদ্ধতিতে কাজ করে। মানে ইনপুট অ্যারে টাকে কতগুলো ক্ষুদ্র ক্ষুদ্র সাব-প্রবলেমে ভাগ করে ফেলে,তারপর সেই ক্ষুদ্র ক্ষুদ্র অংশ গুলো কে মার্জ করে যে সমাধাণ গুলো পায়,সেগুলো একত্রিত করে মূল সর্টেড অ্যারে প্রডিউস করে।
ধর,নিচের অ্যারে টাকেই সর্ট করতে হবে।
এখন এই অ্যারে টাকে আমরা Left এবং Right নামে সমান দুই ভাগে ভাগ করব।
এখন কেউ যদি কোনভাবে আমাদের কে এই Left[] এবং Right[] সাব-অ্যারে দুটি সর্ট করে দেয় তাহলে কিভাবে আমরা এই দুটি সর্টেড সাব-অ্যারে কে মার্জ করে মূল অ্যারে কে সর্ট করতে পারি,সেটাই আগে দেখব।ঐ সাব-অ্যারে দুটি কিভাবে সর্ট করব সেটা এখন ভাবনার বিষয় না।আপাততঃ ধরে নাও কোন এক অলৌকিক শক্তি দিয়ে আমরা সেটা করতে পারব😎।
