যেহেতু আমরা বিভক্তি এবং জয়(ডিভাইড অ্যান্ড কনকার) পদ্ধতি ব্যবহার করে সাজাবো, আমাদের ঠিক করে নিতে হবে ছোট সমস্যাগুলো কেমন হবে। সম্পূর্ণ সমস্যাটি হল একটি পুরো অ্যারেকে সাজানো। ধরি ছোট সমস্যা হবে সাবঅ্যারেকে সাজানো। বিশেষ করে, আমরা ছোট সমস্যাটাকে এভাবে চিন্তা করব, একটি সাবঅ্যারের p থেকে r পর্যন্ত উপাদানগুলো সাজাতে হবে। সাবঅ্যারের জন্য একটি চিহ্ন ব্যবহার করলে ভালো হয়, তো আমরা বলতে পারি array[p..r] হল ওই অ্যারের সাবঅ্যারে। লক্ষ্য কর এই "দুই-ডট" চিহ্ন প্রকৃত জাভাস্ক্রিপ্ট নয়; আমরা এটা শুধু অ্যালগোরিদম বর্ণনা করার জন্য ব্যবহার করব, অ্যালগোরিদমকে কোড আকারে প্রকাশ করার জন্য নয়। আমাদের চিহ্নের সাপেক্ষে, n উপাদান বিশিষ্ট একটি অ্যারের জন্য, আমরা বলতে পারি মূল সমস্যাটি হল array[0..n-1] কে সাজানো।
মার্জসর্ট যেভাবে বিভক্তি এবং জয় পদ্ধতি ব্যবহার করে:
  1. ডিভাইড কর p এবং r মাঝে অবস্থিত q সংখ্যাটি দিয়ে। এই ধাপটি আমরা একই উপায়ে করতে পারি যেভাবে আমরা বাইনারি সার্চে মধ্যবিন্দু বের করেছিলাম: p এবং r যোগ করে, 2 দিয়ে ভাগ করি এবং রাউন্ড করে নেই।
  2. কনকার বিভক্তকরন ধাপে যেই দুটি ছোট সমস্যা তৈরি হয়েছে সেই সাবঅ্যারেগুলোকে বারবার সাজাতে হবে। যেটা হল, সাবঅ্যারে array[p..q] এবং সাবঅ্যারে array[q+1..r] কে বারাবার সাজানো।
  3. একত্রকরণ (কমবাইন) দুইটি সাজানো সাবঅ্যারেকে একসাথে মিলিয়ে একটি সাজানো সাবঅ্যারে array[p..r] তৈরি করা।
আমাদের একটি বেস কেস দরকার। বেস কেস হল একটি সাবঅ্যারে যার উপাদান দুইয়ের কম, এটা হয় যখন p, is greater than or equal to, r, কারণ কোন সাবঅ্যারে যার একটি উপাদান আছে বা কোন উপাদান নেই সেটা সাজানোই আছে। তাহলে আমরা বিভক্তকরন-জয়-একত্রকরণ করব শুধুমাত্র যখন p, is less than, r
চল একটি উদাহরণ দেখি। ধরি একটি অ্যারেতে আছে [14, 7, 3, 12, 9, 11, 6, 2], তো প্রথম সাবঅ্যারেটি হবে সম্পূর্ণ অ্যারে, array[0..7] (p, equals, 0 and r, equals, 7)। এই সাবঅ্যারেতে কমপক্ষে দুইটি উপাদান আছে, আর তাই এটা বেস কেস হবে না।
  • বিভক্তকরন ধাপে, আমরা গণনা করে পাই q, equals, 3
  • জয় ধাপে আমাদের দুইটি সাবঅ্যারেকে সাজাতে হবে, array[0..3] যেটাতে আছে [14, 7, 3, 12] এবং array[4..7] যেটাতে আছে [9, 11, 6, 2]। যখন আমরা জয় ধাপ শেষ করব, দুইটি সাবঅ্যারের প্রত্যেকেই সাজানো থাকবে: array[0..3] তে আছে [3, 7, 12, 14] এবং array[4..7] তে আছে [2, 6, 9, 11], তাহলে পুরো অ্যারেটি হবে [3, 7, 12, 14, 2, 6, 9, 11]।
  • সবশেষে, একত্রকরণ ধাপে দুইটি সাজানো সাবঅ্যারেকে প্রথম অর্ধেক এবং দ্বিতীয় অর্ধেকে মিলিয়ে নিয়ে, চূড়ান্ত সাজানো অ্যারে তৈরি করব [2, 3, 6, 7, 9, 11, 12, 14]।
array[0..3] সাবঅ্যারেটি কিভাবে সাজানো হল? সেই একই উপায়ে। এর দুইয়ের অধিক উপাদান আছে, আর তাই এটা বেস কেস না। এখানে p, equals, 0 এবং r, equals, 3, পেলাম q, equals, 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, equals, 0 এবং r, equals, 1, পেলাম q, equals, 0, array[0..0] যা ([14]) এবং array[1..1] যা ([7]) কে বারবার সাজানো হবে, আমরা পাব array[0..1] যেটাতে থাকবে [14, 7] এবং প্রথম অর্ধেকের সাথে পরের অর্ধেক মিলিয়ে, পেলাম [7, 14]।
array[0..0] এবং array[1..1] সাবঅ্যারে দুইটি হল বেস কেস, যেহেতু প্রত্যেকের দুইয়ের কম উপাদান আছে। এখানে দেখানো হয়েছে কিভাবে মার্জসর্ট অ্যালগোরিদম কাজ করে:
মার্জ সর্ট
মার্জসর্টের অধিকাংশ ধাপ বেশ সহজ। তুমি সহজেই বেস কেস যাচাই করতে পারো। বিভক্তিকরণ ধাপে মধ্যবিন্দু q বের করাও বেশ সহজ। জয় ধাপে দুইটি রিকার্সিভ কল করতে হবে। একত্রকরণ ধাপে আসলে প্রকৃত কাজটুকু করতে হবে, যেখানে তোমাকে দুইটি সাজানো সাবঅ্যারে সংযুক্ত করতে হবে। এখনকার জন্য, ধরি আমরা জানি কিভাবে দুইটি সাজানো সাবঅ্যারেকে কার্যকরভাবে সংযুক্ত করা যায় এবং সম্পূর্ণ মার্জসর্টের উপর মনোযোগ দেই।

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