মার্জ সর্ট ও এর অ্যানালাইসিস

১ · মার্জ সর্ট — সংক্ষিপ্ত রিক্যাপ

মার্জ সর্টের মেকানিক্স (ডিভাইড: অ্যারেকে মাঝখান থেকে দুই ভাগ করা; কনকার: প্রতিটি অর্ধেক রিকার্সিভভাবে সর্ট করা; কমবাইন: দুটি সর্টেড অর্ধেক একত্রে মার্জ করা) ইতিমধ্যে DSA কোর্সে ইমপ্লিমেন্টেশনসহ কভার করা হয়েছে — এখানে সেই মেকানিক্স পুনরায় ব্যাখ্যা না করে সরাসরি এর রানটাইম অ্যানালাইসিসে যাওয়া হচ্ছে, যা L14-এ সাধারণভাবে দেখা D&C টেমপ্লেটের একটি নির্দিষ্ট প্রয়োগ।

২ · রিকারেন্স ডেরিভেশন — $T(n) = 2T(n/2) + O(n)$

মার্জ সর্টের রানটাইম $T(n)$-কে তিনটি অংশে ভাঙা যায়:

• ডিভাইড: অ্যারেকে মাঝখান থেকে ভাগ করা — $O(1)$ (শুধু একটি ইনডেক্স হিসাব)।
• কনকার: দুটি অর্ধেক, প্রতিটির আকার $n/2$, রিকার্সিভভাবে সর্ট করা — $2T(n/2)$।
• কমবাইন: দুটি সর্টেড অর্ধেক মার্জ করা — মোট $n$টি এলিমেন্টের প্রতিটি একবার করে দেখতে হয়, তাই $O(n)$।

এই তিনটি একত্র করলে:

এটি ঠিক সেই ফর্ম $T(n) = aT(n/b) + f(n)$ যার জন্য L13-এ মাস্টার থিওরেম শেখা হয়েছে, যেখানে $a = 2$, $b = 2$, এবং $f(n) = \Theta(n)$। মাস্টার থিওরেম প্রয়োগ করতে প্রথমে $n^{\log_b a}$ হিসাব করা হয়:

যেহেতু $f(n) = \Theta(n) = \Theta(n^{\log_b a})$ (অর্থাৎ $f(n)$ এবং $n^{\log_b a}$ একই গ্রোথ রেটের, $k = 0$ সহ), এটি মাস্টার থিওরেমের কেস ২-এর সাথে মেলে, যা বলে:

অর্থাৎ মার্জ সর্ট $\Theta(n \log n)$ সময়ে চলে — সবসময়, ইনপুট যেভাবেই সাজানো থাক না কেন (এমনকি ইতিমধ্যে সর্টেড ইনপুটেও, কারণ রিকার্সন ও মার্জ ধাপ ইনপুটের ক্রম নির্বিশেষে একইভাবে ঘটে) — এটি L16-এ দেখা কুইক সর্টের সাথে একটি গুরুত্বপূর্ণ পার্থক্য, যেখানে ওয়ার্স্ট ও অ্যাভারেজ কেস ভিন্ন হয়।

৩ · সঠিক তুলনার সংখ্যা — একটি পৃথক রিকারেন্স

"$\Theta(n)$" শুধু গ্রোথ-ক্লাস বলে, প্রকৃত সংখ্যা নয়। মার্জ ধাপে ঠিক কতটি তুলনা (comparison) হয় তা নির্ভুলভাবে গুনতে পারলে বিশ্লেষণ আরও কংক্রিট হয়। দুটি সর্টেড অর্ধেক, আকার $p$ ও $q$ ($p + q = n$), মার্জ করতে সর্বোচ্চ $p + q - 1$টি তুলনা লাগে — কারণ প্রতিটি তুলনায় একটি এলিমেন্ট চূড়ান্ত ফলাফলে বসে যায়, এবং যখন একটি অর্ধেক পুরোপুরি শেষ হয়ে যায় তখন বাকি অর্ধেকের অবশিষ্ট এলিমেন্টগুলো আর কোনো তুলনা ছাড়াই সরাসরি যোগ হয়ে যায় (তাই $n$টি এলিমেন্টে ঠিক $n-1$টি নয়, সর্বোচ্চ $n-1$টি তুলনা)। তাই তুলনার সংখ্যা $C(n)$-এর নিজস্ব রিকারেন্স:

এই রিকারেন্সও $f(n) = \Theta(n)$ সহ একই মাস্টার থিওরেম কেস ২-তে পড়ে, তাই $C(n) = \Theta(n \log n)$ — $T(n)$-এর মতোই। নিচের কোড সেলে এই $C(n)$ সত্যিকারের কোড চালিয়ে গুনে দেখানো হচ্ছে।

import random
import math

def merge_sort_counted(arr):
    """মার্জ সর্ট চালায় এবং মার্জ ধাপে ঠিক কতটি তুলনা হলো তা ফেরত দেয়।"""
    counter = [0]

    def merge(left, right):
        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            counter[0] += 1
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result.extend(left[i:])
        result.extend(right[j:])
        return result

    def sort(a):
        if len(a) <= 1:
            return a
        mid = len(a) // 2
        left = sort(a[:mid])
        right = sort(a[mid:])
        return merge(left, right)

    sorted_arr = sort(arr)
    return sorted_arr, counter[0]

random.seed(42)
sizes = [100, 200, 400, 800]

print(f"{'n':>5} | {'সঠিক?':>7} | {'তুলনা':>8} | {'n*log2(n)':>10} | {'রেশিও':>8}")
for n in sizes:
    arr = list(range(n))
    random.shuffle(arr)
    sorted_arr, comparisons = merge_sort_counted(arr)
    correct = (sorted_arr == sorted(arr))
    n_log_n = n * math.log2(n)
    ratio = comparisons / n_log_n
    print(f"{n:>5} | {str(correct):>7} | {comparisons:>8} | {n_log_n:>10.1f} | {ratio:>8.4f}")