মার্জ সর্ট (Merge Sort)

আপনার ডেস্কে থাকা কাগজপত্রের একটি বিশাল অগোছালো স্তূপের কথা ভাবুন। এটিকে দুটি ছোট স্তূপে ভাগ করা বেশ সহজ। যদি প্রতিটি ছোট স্তূপ আগে থেকেই সাজানো (sorted) থাকে, তবে সেগুলোকে একত্রিত (merge) করে আবার একটি সাজানো স্তূপে পরিণত করাও সহজ — শুধু প্রতিটি স্তূপের সবচেয়ে ওপরের কাগজটি তুলনা করুন এবং ছোটটি তুলে নিন। ঠিক এভাবেই মার্জ সর্ট (Merge Sort) কাজ করে।

অবশ্যই, ছোট স্তূপগুলো প্রথম দিকে সাজানো থাকে না — তাই আপনি সেগুলোকে আবারও ভাগ করেন, এবং ততক্ষণ পর্যন্ত ভাগ করতে থাকেন যতক্ষণ না প্রতিটি স্তূপে কেবল একটি করে কাগজ থাকে। একটিমাত্র কাগজ সর্বদা সাজানোই থাকে। এরপর জোড়ায় জোড়ায় স্তূপগুলোকে আবার একত্রিত (merge) করে ওপরের দিকে নিয়ে আসুন। পুরো প্রক্রিয়াটি \(O(n \log n)\) সময়ে কাজ করে — এবং এটি শতভাগ নিশ্চিত, ইনপুট যেমনই হোক না কেন।

তিনটি ধাপ (The Three Phases)

১. ভাগ করুন (Divide): অ্যারেটিকে সমান দুই ভাগে ভাগ করুন। প্রতিটি অর্ধাংশের ওপর রিকার্শন (recursion) প্রয়োগ করুন। যতক্ষণ না অ্যারের সাইজ ১ (base case) হচ্ছে, ততক্ষণ ভাগ করতে থাকুন।

২. জয় করুন (Conquer): ১ সাইজের অ্যারেগুলো স্বাভাবিকভাবেই সাজানো (sorted) থাকে। আসল কাজটি এরপরই শুরু হয়।

৩. একত্রিত করুন (Merge): দুটি সাজানো অর্ধাংশকে একত্রিত করে একটি সম্পূর্ণ সাজানো অ্যারে তৈরি করুন। দুটি পয়েন্টার ব্যবহার করুন — প্রতিটি অর্ধাংশের জন্য একটি। প্রতিটি ধাপে, সামনের ছোট উপাদানটি (element) বেছে নিন এবং সেই পয়েন্টারটিকে এক ধাপ এগিয়ে দিন। যখন একটি অর্ধাংশ শেষ হয়ে যাবে, তখন অন্য অর্ধাংশের বাকি অংশটুকু শেষে যোগ করে দিন। প্রতিটি মার্জের জন্য \(O(n)\) সময় লাগে, এবং প্রতিটি উপাদান ঠিক log n সংখ্যক মার্জে অংশ নেয় (রিকার্শন ট্রির প্রতিটি লেভেলে একবার করে)।

কেন এটি সর্বদা \(O(n \log n)\)?

রিকার্শন ট্রিতে log n সংখ্যক লেভেল থাকে (কারণ আমরা প্রতিবার সমস্যাটিকে অর্ধেক করে ফেলি)। প্রতিটি লেভেলে, সমস্ত নোড মিলিয়ে মোট মার্জের কাজ হয় \(O(n)\) — অর্থাৎ অনেকগুলি ছোট ছোট মার্জ মিলে প্রতিটি উপাদানকে একবার স্পর্শ করে। গুণ করলে পাই: \(O(n)\) × \(O(\log n)\) = \(O(n \log n)\), এটি সর্বদা সত্যি — কোনো খারাপ ইনপুট বা ভুল পিভট (pivot) বাছাইয়ের ভয় এখানে নেই।

স্থায়িত্ব (Stability) এবং মেমরি বা স্পেস ট্রেডঅফ

মার্জ সর্ট একটি স্টেবল (stable) অ্যালগরিদম: একত্রিত বা মার্জ করার সময় যখন দুটি উপাদান সমান হয়, তখন আমরা সর্বদা বাম দিকের (বা আগের) অর্ধাংশ থেকে উপাদানটি আগে নিই। ফলে সমান উপাদানগুলো নিজেদের মধ্যে কখনো স্থান পরিবর্তন করে না।

এর একমাত্র নেতিবাচক দিকটি হলো মার্জ বাফারের জন্য এর \(O(n)\) অতিরিক্ত মেমরি (extra space) প্রয়োজন হয়। মেমরি-সীমাবদ্ধ ডিভাইসে কুইক সর্টের কাছে মার্জ সর্টের হেরে যাওয়ার এটিই মূল কারণ। তবে এর একটি ব্যতিক্রম আছে: লিংকড লিস্ট (linked lists)। দুটি সাজানো লিংকড লিস্ট একত্রিত করার জন্য কোনো অতিরিক্ত অ্যারের প্রয়োজন হয় না — শুধু পয়েন্টারগুলো রিলিংক (relink) করলেই হয়। তাই লিংকড লিস্টে মার্জ সর্ট ব্যবহার করলে কেবল স্ট্যাক স্পেসের জন্য \(O(\log n)\) মেমরি লাগে।

মার্জ সর্ট হলো টিমসর্ট বা Timsort এর মূল ভিত্তি (যা অবজেক্ট সাজানোর জন্য Python এবং Java ব্যবহার করে) এবং এটি এক্সটার্নাল সর্টিং বা external sorting এর (সাধারণ র‍্যামের চেয়ে বড় সাইজের ডেটা যা হার্ডডিস্কে থাকে) স্ট্যান্ডার্ড অ্যালগরিদম।