Merge sort — ভাগ করা, সাজানো, জোড়া দেওয়া

১ · আবার divide and conquer — পরীক্ষার খাতা সাজানোর গল্প

একটি কলেজের পরীক্ষা শেষ। ৪০০টি খাতা রোল নম্বর অনুযায়ী সাজাতে হবে, আর হাতে আছে আটজন সহকারী। একজনকে পুরো স্তূপ দিলে তিনি পর্ব ২০-এর insertion sort-এর মতো একটি একটি খাতা নিয়ে ঠিক জায়গায় ঢোকাবেন — শেষের দিকে প্রতিটি খাতার জন্য শত শত খাতা পেরোতে হবে। চালাক পরীক্ষা-নিয়ন্ত্রক অন্যভাবে ভাবেন: স্তূপটি আট ভাগ করে আটজনকে দিন। প্রত্যেকে নিজের ৫০টি খাতা সাজাবেন। তারপর দুজন দুজন করে দুটি সাজানো স্তূপ জোড়া দেবেন — দুটি স্তূপের ওপরের খাতা দেখে ছোট রোলেরটি নতুন স্তূপে রাখা, বারবার। চারটি স্তূপ হবে, তারপর দুটি, তারপর একটি।

এই চিন্তার নাম divide and conquer, যা পর্ব ০৮ আর ০৯-এ recurrence হিসেবে দেখেছেন। তিনটি ধাপ:

1. ভাগ (divide): সমস্যাকে ছোট উপ-সমস্যায় ভাঙা — অ্যারের বাঁ অর্ধেক আর ডান অর্ধেক।
2. জয় (conquer): উপ-সমস্যাগুলো একই পদ্ধতিতে, রিকার্শন দিয়ে সমাধান করা। খুব ছোট হলে (০ বা ১টি উপাদান) সরাসরি উত্তর — এটিই base case.
3. জোড়া (combine): ছোট উত্তরগুলো মিলিয়ে বড় উত্তর বানানো — দুটি সাজানো অর্ধেক merge করা।

Merge sort-এর বিশেষত্ব হলো, ভাগ করা প্রায় বিনা খরচে হয় (শুধু মাঝখানের index বের করা), আর সব বুদ্ধি থাকে জোড়া দেওয়ার ধাপে। পর্ব ২২-এর quick sort ঠিক উল্টো: সেখানে ভাগ করাতেই সব কাজ, জোড়া দিতে কিছুই লাগে না। এই দুটি অ্যালগরিদম পাশাপাশি রাখলে divide and conquer-এর দুটি মুখ পরিষ্কার দেখা যায়।

শেষ সারির পার্থক্যটি দেখুন: দশ লাখ সংখ্যায় প্রায় পঁচিশ হাজার গুণ কম কাজ। এক সেকেন্ডে কয়েক কোটি সরল কাজ করতে পারে এমন কম্পিউটারে insertion sort-এর worst case লাগবে কয়েক ঘণ্টা, merge sort-এর এক সেকেন্ডেরও কম। Big-O-র ভাষা (পর্ব ০৪) এখানে শুধু তত্ত্ব নয় — সময়সীমার ভেতরে উত্তর আসবে কি না, তার পার্থক্য।

২ · Merge — দুটি সাজানো সারি এক সারিতে

ধরুন ব্যাংকের দুটি কাউন্টারের সামনে দুটি সারি, প্রতিটি সারি টোকেন নম্বর অনুযায়ী আগে থেকেই সাজানো। এখন দুটি কাউন্টার এক করে একটিই সারি বানাতে হবে, নম্বরের ক্রম ঠিক রেখে। উপায় সহজ: দুই সারির সামনের দুজনের টোকেন দেখুন, ছোট নম্বরের জনকে নতুন সারিতে পাঠান। তাঁর সারিতে পরের জন সামনে এলেন। আবার তুলনা। একটি সারি ফুরিয়ে গেলে অন্য সারির বাকি সবাই একসাথে চলে যাবেন — তাঁরা তো আগে থেকেই সাজানো।

কোডে দুই সারির সামনের জনকে চিহ্নিত করে দুটি index: বাঁ অংশে i, ডান অংশে j — পর্ব ১৬-এর two pointer কৌশল। আমরা half-open রেঞ্জ ব্যবহার করব: বাঁ অংশ a[lo..mid), ডান অংশ a[mid..hi) — শুরু অন্তর্ভুক্ত, শেষ নয়।

Pseudocode — merge a[lo..mid) and a[mid..hi), both already sorted (0-based)

i = lo; j = mid; k = lo
while i < mid and j < hi:
    if a[i] <= a[j]:            // "<=" : on a tie take the LEFT one (stability)
        buf[k] = a[i]; i = i + 1
    else:
        buf[k] = a[j]; j = j + 1
    k = k + 1
copy the rest of a[i..mid) to buf[k..]     // at most one of these two is non-empty
copy the rest of a[j..hi)  to buf[k..]
copy buf[lo..hi) back to a[lo..hi)

এবার বাঁ অংশ L = [2, 4, 5, 7] আর ডান অংশ R = [1, 2, 3, 6] merge করে দেখুন। দুটি 2 আছে — কোনটি কোন দিক থেকে এল, তা চিনতে লিখছি 2L আর 2R.

কেন merge সঠিক — loop invariant

পর্ব ০৩-এর loop invariant পদ্ধতিতে প্রমাণ করি। দাবি: while লুপের প্রতিটি ঘূর্ণনের শুরুতে

• (ক) buf[lo..k)-এ আছে L আর R মিলিয়ে সবচেয়ে ছোট k − lo টি উপাদান, সাজানো ক্রমে;
• (খ) a[i] হলো L-এর বাকি উপাদানগুলোর মধ্যে সবচেয়ে ছোট, আর a[j] R-এর বাকিগুলোর মধ্যে সবচেয়ে ছোট (যদি বাকি থাকে)।

শুরুতে (initialization): k = lo, buf-এর অংশটি খালি — (ক) ফাঁকা অর্থে সত্য। i = lo আর j = mid দুই সাজানো অংশের প্রথম ঘর, তাই (খ) সত্য।

প্রতি ধাপে বজায় থাকে (maintenance): ধরুন a[i] <= a[j]. বাকি সব উপাদান হয় L-এর বাকি অংশে (সবাই ≥ a[i], কারণ L সাজানো), নয়তো R-এর বাকি অংশে (সবাই ≥ a[j] ≥ a[i]). তাই a[i]-ই বাকিদের মধ্যে সবচেয়ে ছোট। আর (ক) অনুযায়ী buf-এ আগে থেকে থাকা প্রতিটি উপাদান বাকিদের যেকোনোটির চেয়ে বড় নয় — তাই a[i]-কে buf-এর শেষে বসালে buf সাজানোই থাকে। i আর k এক বাড়লে (ক) আর (খ) আবার সত্য। অন্য ক্ষেত্রটি (a[j] ছোট) একইভাবে।

শেষে (termination): প্রতি ঘূর্ণনে i বা j এক বাড়ে, তাই সর্বোচ্চ (mid − lo) + (hi − mid) ঘূর্ণনে লুপ থামে। থামার সময় একটি অংশ খালি; অন্য অংশের বাকি উপাদানগুলো নিজেরা সাজানো আর (ক) অনুযায়ী buf-এর সবার চেয়ে বড় বা সমান — তাই সরাসরি কপি করলে পুরো buf সাজানো। প্রমাণ শেষ।

খরচ: প্রতিটি উপাদান ঠিক একবার buf-এ যায় আর একবার ফেরত আসে, তাই m + n উপাদানের merge-এ সময় Θ(m + n). তুলনার সংখ্যা সবচেয়ে কম min(m, n) (যখন ছোট অংশের সবাই অন্যটির প্রথম উপাদানের চেয়ে ছোট, যেমন [1 2] আর [8 9]: তুলনা ২টি, তারপর বাকিটা কপি), আর সবচেয়ে বেশি m + n − 1 (যখন দুই অংশ একে অপরের ফাঁকে ফাঁকে বসে, যেমন ওপরের উদাহরণ — শেষ উপাদানটি ছাড়া প্রতিটির জন্য একটি তুলনা)।

Stability — কেন “<=”, “<” নয়

Stable sort মানে সমান key-এর উপাদানগুলোর আগের আপেক্ষিক ক্রম বদলায় না। কেন দরকার? ধরুন bKash-এর লেনদেনের তালিকা আগে সময় অনুযায়ী সাজানো, এখন আপনি সেটি টাকার অঙ্ক অনুযায়ী সাজাবেন। Stable sort হলে একই অঙ্কের লেনদেনগুলো সময়ের ক্রমেই থাকবে — দুই ধাপে দুই key-তে সাজানো সম্ভব হয় (পর্ব ২৫-এ বিস্তারিত)।

প্রমাণ (induction): দাবি — merge sort যেকোনো অংশ সাজানোর পর সমান key-এর উপাদানগুলো মূল ক্রমেই থাকে। ০ বা ১টি উপাদানে এটি স্পষ্ট। বড় অংশে, রিকার্শনের পর (inductive hypothesis) প্রতিটি অর্ধেকের ভেতরে সমান উপাদানগুলো মূল ক্রমে আছে। এখন merge দেখুন। একই অর্ধেকের দুটি সমান উপাদান সেই অর্ধেকের ক্রমেই বের হয়, কারণ pointer শুধু সামনে এগোয়। আর দুই অর্ধেকের দুটি সমান উপাদান x (বাঁ থেকে) আর y (ডান থেকে) — মূল অ্যারেতে x ছিল y-এর আগে, কারণ পুরো বাঁ অর্ধেক ডান অর্ধেকের আগে। ধরুন উল্টোটা ঘটল, y আগে বের হলো। সেই মুহূর্তে বাঁ দিকের প্রার্থী a[i] হয় x নিজে, নয়তো x-এর আগের কোনো উপাদান — বাঁ অংশ সাজানো বলে দুই ক্ষেত্রেই a[i] ≤ x = y. কিন্তু ডান থেকে y নেওয়া হয় কেবল তখন, যখন a[i] <= y মিথ্যা, অর্থাৎ a[i] > y — স্ববিরোধ। তাই x সবসময় y-এর আগে বের হয়।

৩ · পুরো অ্যালগরিদম — ভাগ, রিকার্শন, জোড়া

Merge হাতে থাকলে বাকি অ্যালগরিদম তিন লাইনের:

Pseudocode — merge sort on a[lo..hi) (0-based, half-open)

mergeSort(a, lo, hi):
    if hi - lo <= 1: return          // 0 or 1 element: already sorted
    mid = lo + (hi - lo) / 2         // integer division
    mergeSort(a, lo, mid)            // sort the left half
    mergeSort(a, mid, hi)            // sort the right half
    merge(a, lo, mid, hi)            // join the two sorted halves (section 2)

এর শুদ্ধতা strong induction দিয়ে এক অনুচ্ছেদে: n ≤ 1 হলে অংশটি এমনিতেই সাজানো। n ≥ 2 হলে দুই অর্ধেকের আকার n-এর চেয়ে কঠোরভাবে ছোট (⌊n/2⌋ আর ⌈n/2⌉, দুটোই ≥ ১), তাই inductive hypothesis অনুযায়ী রিকার্সিভ ডাক দুটি সেগুলো সঠিকভাবে সাজায়; তারপর অংশ ২-এ প্রমাণিত merge দুটি সাজানো অংশ থেকে একটি সাজানো অংশ বানায়। আকার প্রতিবার কমে বলে রিকার্শন থামেও।

এবার ৮টি উপাদানের [5, 2, 4, 7, 1, 3, 2, 6]-এ পুরো recursion tree দেখুন। আসলে রিকার্শন গভীরতা-আগে (depth-first) চলে — বাঁ দিকের পুরো শাখা শেষ করে তবে ডান দিকে যায় — কিন্তু বিশ্লেষণের জন্য স্তর ধরে দেখাই সুবিধাজনক। d = গভীরতা (depth).

এবার কোডে চালিয়ে দেখুন। প্রোগ্রামটি প্রতিটি merge ছাপায়, গভীরতা অনুযায়ী ডানে সরিয়ে — ফলে আসল (depth-first) ক্রমটিও দেখা যাবে। একটি মাত্র buf অ্যারে শুরুতে একবার বানানো হয়েছে, সব ডাক সেটিই ভাগ করে ব্যবহার করে:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long comps = 0;

string show(const vector<int>& a, int lo, int hi) {
    string s = "[";
    for (int i = lo; i < hi; ++i) s += (i > lo ? " " : "") + to_string(a[i]);
    return s + "]";
}

void mergeSort(vector<int>& a, vector<int>& buf, int lo, int hi, int depth, bool verbose) {
    if (hi - lo <= 1) return;                       // 0 or 1 element: already sorted
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, buf, lo, mid, depth + 1, verbose);
    mergeSort(a, buf, mid, hi, depth + 1, verbose);
    string before = string(2 * depth, ' ') + "merge " + show(a, lo, mid) + " + " + show(a, mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        ++comps;
        if (a[i] <= a[j]) buf[k++] = a[i++];        // <= : take from the left on ties (stable)
        else              buf[k++] = a[j++];
    }
    while (i < mid) buf[k++] = a[i++];              // copy whatever is left (one part is empty)
    while (j < hi)  buf[k++] = a[j++];
    for (k = lo; k < hi; ++k) a[k] = buf[k];
    if (verbose) cout << before << " -> " << show(a, lo, hi) << '\n';
}
long long sortAndCount(vector<int>& a, bool verbose = false) {
    comps = 0;
    vector<int> buf(a.size());                      // one buffer, allocated once
    mergeSort(a, buf, 0, (int)a.size(), 0, verbose);
    return comps;
}
int main() {
    vector<int> a{5, 2, 4, 7, 1, 3, 2, 6}, s{1, 2, 3, 4, 5, 6, 7, 8}, r{8, 7, 6, 5, 4, 3, 2, 1};
    long long c = sortAndCount(a, true);
    cout << "sorted: " << show(a, 0, (int)a.size()) << ", comparisons: " << c << '\n';
    cout << "already sorted: comparisons = " << sortAndCount(s) << '\n';
    cout << "reversed: comparisons = " << sortAndCount(r) << '\n';
}

    merge [5] + [2] -> [2 5]
    merge [4] + [7] -> [4 7]
  merge [2 5] + [4 7] -> [2 4 5 7]
    merge [1] + [3] -> [1 3]
    merge [2] + [6] -> [2 6]
  merge [1 3] + [2 6] -> [1 2 3 6]
merge [2 4 5 7] + [1 2 3 6] -> [1 2 2 3 4 5 6 7]
sorted: [1 2 2 3 4 5 6 7], comparisons: 17
already sorted: comparisons = 12
reversed: comparisons = 12

comps = 0

def show(a, lo, hi):
    return "[" + " ".join(map(str, a[lo:hi])) + "]"

def merge_sort(a, buf, lo, hi, depth, verbose):
    global comps
    if hi - lo <= 1:                      # 0 or 1 element: already sorted
        return
    mid = (lo + hi) // 2
    merge_sort(a, buf, lo, mid, depth + 1, verbose)
    merge_sort(a, buf, mid, hi, depth + 1, verbose)
    before = "  " * depth + "merge " + show(a, lo, mid) + " + " + show(a, mid, hi)
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        comps += 1
        if a[i] <= a[j]:                  # <= : take from the left on ties (stable)
            buf[k] = a[i]; i += 1
        else:
            buf[k] = a[j]; j += 1
        k += 1
    buf[k:hi] = a[i:mid] + a[j:hi]        # copy whatever is left (one part is empty)
    a[lo:hi] = buf[lo:hi]
    if verbose:
        print(before, "->", show(a, lo, hi))

def sort_and_count(a, verbose=False):
    global comps
    comps = 0
    merge_sort(a, [0] * len(a), 0, len(a), 0, verbose)
    return comps

a = [5, 2, 4, 7, 1, 3, 2, 6]
c = sort_and_count(a, True)
print(f"sorted: {show(a, 0, len(a))}, comparisons: {c}")
for name, b in [("already sorted", [1, 2, 3, 4, 5, 6, 7, 8]),
                ("reversed", [8, 7, 6, 5, 4, 3, 2, 1])]:
    print(f"{name}: comparisons = {sort_and_count(b)}")

    merge [5] + [2] -> [2 5]
    merge [4] + [7] -> [4 7]
  merge [2 5] + [4 7] -> [2 4 5 7]
    merge [1] + [3] -> [1 3]
    merge [2] + [6] -> [2 6]
  merge [1 3] + [2 6] -> [1 2 3 6]
merge [2 4 5 7] + [1 2 3 6] -> [1 2 2 3 4 5 6 7]
sorted: [1 2 2 3 4 5 6 7], comparisons: 17
already sorted: comparisons = 12
reversed: comparisons = 12

৪ · বিশ্লেষণ — কেন Θ(n log n), আর তুলনা ঠিক কতটি

n টি উপাদান সাজাতে সময় T(n) ধরি। মাঝখান বের করা Θ(1), দুটি রিকার্সিভ ডাক T(⌊n/2⌋) + T(⌈n/2⌉), আর merge Θ(n). পর্ব ০৮-এর মতো floor-ceiling সরিয়ে পাই পরিচিত recurrence:

তিনভাবে সমাধান:

• Recursion tree (পর্ব ০৮): merge-এর খরচ cn ধরলে স্তর d-তে 2^d টি অংশ, প্রতিটির আকার n/2^d, তাই স্তরের মোট খরচ 2^d · c(n/2^d) = cn — প্রতিটি স্তরে সমান! স্তর আছে lg n টি (0 থেকে lg n − 1), সাথে তলায় n টি base case. মোট cn lg n + Θ(n) = Θ(n log n). ওপরের ডায়াগ্রামে প্রতিটি merge-স্তরে ঠিক ৮টি উপাদান কপি হয়েছিল — এটিই সেই “প্রতি স্তরে n”.
• Master theorem (পর্ব ০৯): a = 2, b = 2, তাই watershed n^log₂2 = n. f(n) = Θ(n) তার সমান — case 2, উত্তর Θ(n log n).
• Substitution: n = 2^k আর T(n) = 2T(n/2) + n, T(1) = 0 হলে induction-এ T(n) = n lg n ঠিক। যাচাই: 2 · (n/2) lg(n/2) + n = n(lg n − 1) + n = n lg n.

লক্ষ করুন, recurrence-টি ইনপুটের মান দেখে না — ভাগ সবসময় মাঝখানে, merge সবসময় Θ(n). তাই merge sort-এর best case, average আর worst case তিনটিই Θ(n log n). Quick sort-এর মতো খারাপ ইনপুটে Θ(n²) হয়ে যাওয়ার ভয় নেই — এই নিশ্চয়তাই merge sort-এর বড় শক্তি।

তুলনার নিখুঁত হিসাব

বিশ্ববিদ্যালয়ের পরীক্ষায় প্রায়ই Θ ছাড়িয়ে নিখুঁত সংখ্যা চাওয়া হয়। n = 2^k হলে:

• Worst case: প্রতিটি merge-এ (m + m) উপাদানে সর্বোচ্চ 2m − 1 তুলনা। স্তর d-তে 2^d টি merge, প্রতিটিতে n/2^d − 1 টি — স্তরের মোট n − 2^d. d = 0 থেকে k − 1 যোগ করলে: kn − (2^k − 1) = n lg n − n + 1. n = 8: 24 − 8 + 1 = 17 — ঠিক আমাদের অ্যারের সংখ্যা।
• Best case: প্রতিটি merge-এ সর্বনিম্ন m তুলনা, স্তরের মোট n/2, তাই (n/2) lg n. n = 8: 12 — সাজানো আর উল্টো অ্যারের সংখ্যা।
• যেকোনো n-এর worst case: W(n) = n⌈lg n⌉ − 2^{⌈lg n⌉} + 1 (Knuth-এর বইয়ে প্রমাণ আছে)। n = 2^k হলে এটি ওপরের সূত্রে নেমে আসে।

ছোট n-এর জন্য সব permutation চালিয়ে (brute force) পাওয়া আসল সংখ্যা, আর তুলনা-ভিত্তিক যেকোনো সর্টের তাত্ত্বিক নিম্নসীমা ⌈lg n!⌉ (পর্ব ২৪-এ প্রমাণ হবে):

অর্থাৎ worst case-এ merge sort তাত্ত্বিক সেরার খুব কাছে — n = 4-এ ঠিক সমান, n = 5…8-এ মাত্র ১টি বেশি। বড় n-এ lg n! ≈ n lg n − 1.44n, আর merge sort-এর worst case n lg n − n-এর কাছাকাছি — পার্থক্য প্রতি উপাদানে অর্ধেকেরও কম তুলনা। এজন্যই তুলনা যখন খুব ব্যয়বহুল (যেমন লম্বা string বা জটিল comparator), তখন merge-ভিত্তিক সর্ট জনপ্রিয় — ভাবনার প্রশ্ন ২ আর ৪ দেখুন।

৫ · জায়গার হিসাব — Θ(n) buffer আর Θ(log n) গভীরতা

Merge-এর সময় ফল লেখার জন্য আলাদা জায়গা লাগে — মূল অ্যারেতেই লিখতে গেলে যে উপাদান এখনো পড়া হয়নি, তার ওপর লেখা পড়ে যাবে। তাই অ্যারের merge sort-এর auxiliary space দুই অংশে:

• Buffer: n আকারের একটি অ্যারে — Θ(n). একবার বানিয়ে সব ডাকে ভাগ করে ব্যবহার করলে মোট বরাদ্দও n.
• Recursion stack: একসাথে সর্বোচ্চ যতগুলো ডাক অপেক্ষায় থাকে, অর্থাৎ recursion depth — প্রতিবার আকার অর্ধেক হয় বলে ⌈lg n⌉ + 1, অর্থাৎ Θ(log n). n = 10^৯ হলেও মাত্র ৩১টির মতো frame, তাই এখানে stack overflow-এর ভয় নেই (পর্ব ০৭-এর গভীর রিকার্শনের সাথে তুলনা করুন)।

মোট বাড়তি জায়গা Θ(n) + Θ(log n) = Θ(n). তাই সাধারণ অ্যারের merge sort in-place নয় — insertion sort বা heapsort-এর (পর্ব ২৩) সাথে এটিই বড় পার্থক্য।

বাস্তবের তিনটি উন্নতি

1. ছোট অংশে insertion sort: ১৬–৩২টির মতো ছোট অংশে insertion sort-এর কম overhead আর ভালো cache locality merge sort-এর রিকার্শনের চেয়ে দ্রুত। আকার n ≥ কোনো সীমা হলে ভাগ, নইলে insertion sort — Θ(n log n) অটুট থাকে, ধ্রুবক কমে।
2. আগে থেকে সাজানো হলে merge বাদ: দুই অর্ধেক সাজানোর পর যদি a[mid-1] <= a[mid] হয়, তাহলে পুরো অংশ আগে থেকেই সাজানো — merge করার দরকার নেই। একটি লাইনেই সাজানো ইনপুটে মোট তুলনা n − 1, সময় Θ(n).
3. কপি অর্ধেক করা: প্রতিবার buf থেকে a-তে ফেরত না এনে, স্তরে স্তরে a আর buf-এর ভূমিকা অদলবদল করা যায় — একই কাজ, অর্ধেক কপি।

৬ · Bottom-up merge sort — রিকার্শন ছাড়া, লুপ দিয়ে

Recursion tree-র merge-অংশটি তলা থেকে ওপরে উঠেছিল: আগে ১-১ জোড়া, তারপর ২-২, তারপর ৪-৪. তাহলে ভাগ করার রিকার্শন বাদ দিয়ে সরাসরি তলা থেকেই শুরু করা যায়। প্রথম পাসে পাশাপাশি প্রতিটি ১ উপাদানের অংশ জোড়া দিন, দ্বিতীয় পাসে ২-এর অংশ, তারপর ৪-এর… যতক্ষণ না অংশের মাপ (width) n ছাড়ায়। এর নাম bottom-up merge sort. শেষে একটি অংশ জোড়াহীন থাকতে পারে, বা ছোট হতে পারে — min দিয়ে সীমা কেটে নিলেই সমস্যা নেই।

Pseudocode — bottom-up merge sort (0-based, half-open)

width = 1
while width < n:
    for lo = 0, 2*width, 4*width, ... while lo < n:
        mid = min(lo + width, n)
        hi  = min(lo + 2*width, n)
        merge(a, lo, mid, hi)        // if mid == hi the right part is empty: nothing to do
    width = 2 * width

কখন bottom-up? রিকার্শন নিষেধ বা ব্যয়বহুল এমন পরিবেশে (কিছু embedded সিস্টেম, GPU), আর linked list-এ (পরের অংশ) — যেখানে এটি বাড়তি জায়গা O(1)-এ নামিয়ে আনে। মনে রাখবেন, n দুইয়ের ঘাত না হলে bottom-up আর top-down-এর ভাগ আলাদা হয় (top-down ৭-কে ৩ + ৪-এ ভাঙে, bottom-up ৪ + ৩-এ), তাই তুলনার সংখ্যা সবসময় হুবহু এক হয় না — কিন্তু দুটোই Θ(n log n) আর দুটোই stable.

৭ · Linked list-এর merge sort — যেখানে buffer লাগেই না

অ্যারেতে merge-এর জন্য buffer লাগে, কারণ উপাদান সত্যিই সরাতে হয়। কিন্তু linked list-এ (পর্ব ১২) “সরানো” মানে শুধু next pointer বদলানো। দুটি সাজানো list merge করতে কোনো নতুন node লাগে না — দুই list-এর সামনের node দুটির ছোটটিকে ফলের লেজে জুড়ে দিন, এটুকুই। শেষে যে list বাকি থাকে, তাকে একটি মাত্র pointer দিয়ে পুরোটা জুড়ে দিন — কপি নেই।

struct Node { int val; Node* next; };

Node* mergeLists(Node* a, Node* b) {
    Node dummy{0, nullptr};                 // sentinel: no special case for the first node
    Node* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }   // ties: left list first (stable)
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;                 // append the rest with ONE link -- no copying
    return dummy.next;
}

Node* sortList(Node* head) {
    if (!head || !head->next) return head;  // 0 or 1 node
    Node* slow = head; Node* fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }  // find the middle
    Node* right = slow->next;
    slow->next = nullptr;                   // cut into two lists
    return mergeLists(sortList(head), sortList(right));
}

মাঝখান খুঁজতে পর্ব ১২ ও ১৬-এর fast/slow pointer: fast দুই ঘর এগোয়, slow এক ঘর — fast শেষে পৌঁছালে slow মাঝখানে। dummy হলো একটি sentinel node, যাতে “ফলের প্রথম node কোনটি” আলাদা করে ভাবতে না হয়।

বিশ্লেষণ: প্রতিটি স্তরে মাঝখান খোঁজা আর merge — দুটোই মোট Θ(n), স্তর lg n টি, তাই সময় Θ(n log n). বাড়তি জায়গা: কোনো buffer নেই, শুধু রিকার্শনের Θ(log n) stack. আর bottom-up রূপে (প্রথমে ১-node-এর টুকরো জোড়া, তারপর ২-এর…) সেটুকুও লাগে না — বাড়তি জায়গা O(1).

কেন linked list-এ merge sort-ই স্বাভাবিক পছন্দ?

• শুধু ক্রমানুসারে পড়া: merge দুই list-কে সামনে থেকে পেছনে একবার হাঁটে — linked list ঠিক এটাই ভালো পারে। Heapsort-এর দরকার index দিয়ে লাফানো (2i + 1-তম উপাদান), যা linked list-এ Θ(n) খরচের random access. Binary insertion বা median-of-three pivot বাছাইয়ের মতো কৌশলেও একই সমস্যা।
• Merge-এর একমাত্র দুর্বলতা উধাও: অ্যারেতে merge sort-এর বিরুদ্ধে প্রধান অভিযোগ Θ(n) buffer — linked list-এ সেটি লাগেই না।
• নিশ্চয়তা আর stability: worst case Θ(n log n), আর node সরানো হয় না বলে stable রাখা সহজ।

এজন্যই C++-এর std::list::sort (যা standard অনুযায়ী stable আর মোটামুটি n log n তুলনা করে) সাধারণত merge sort হিসেবে লেখা হয়, আর Linux kernel-এর linked list সাজানোর ফাংশন list_sort-ও একটি merge sort. মনে রাখবেন, std::sort linked list-এ চলেই না — তার random access iterator লাগে।

৮ · External merge sort — RAM-এর চেয়ে বড় ডেটা

একটি টেলিকম কোম্পানির এক মাসের কল-রেকর্ড ২০০ GB, আর সার্ভারের RAM ১৬ GB. পুরো ডেটা একসাথে মেমরিতে আনা অসম্ভব। এখানেও merge sort, কারণ merge ডেটাকে শুধু সামনে থেকে পেছনে ক্রমানুসারে পড়ে — ডিস্ক বা SSD ঠিক এভাবে পড়াতেই সবচেয়ে দ্রুত। এর নাম external sorting, আর ধাপ দুটি:

1. Run বানানো: RAM-এ যতটুকু ধরে (ধরুন ১৬ GB-র মধ্যে নিরাপদে ১০ GB) ততটুকু পড়ুন, মেমরিতেই সাজান (যেকোনো দ্রুত সর্টে), আর ডিস্কে একটি সাজানো ফাইল হিসেবে লিখুন। এমন প্রতিটি সাজানো টুকরোকে বলে run. ২০০ GB থেকে হবে ২০টি run.
2. k-way merge: ২০টি run একসাথে জোড়া দিন। প্রতিটি run-এর সামনের ছোট একটি অংশ মেমরিতে রাখুন। প্রতিবার ২০টি প্রার্থীর মধ্যে সবচেয়ে ছোটটি output ফাইলে লিখুন, আর সেই run থেকে পরের উপাদান আনুন।

দ্বিতীয় ধাপে “k টি প্রার্থীর মধ্যে সবচেয়ে ছোট” প্রতিবার খুঁজতে সরলভাবে k − 1 তুলনা লাগে। দ্রুত উপায় একটি min-heap — পর্ব ২৩-এর priority queue. Heap-এ k টি (মান, run) জোড়া থাকে; সবচেয়ে ছোটটি বের করা আর নতুন একটি ঢোকানো — দুটোই O(log k). এই k-way merge তিনটি ছোট run দিয়ে দেখুন:

মোট খরচ: M = মেমরিতে ধরে এমন উপাদান, N = মোট উপাদান। Run বানাতে O(N log M), k = N/M টি run-এর merge-এ O(N log k) — একসাথে O(N log N) তুলনা। কিন্তু external sort-এ আসল খরচ ডিস্কের পড়া-লেখা: এখানে পুরো ডেটা দুবার পড়া আর দুবার লেখা হয় (প্রতি ধাপে একবার)। Run এত বেশি হলে যে সবার জন্য মেমরিতে জায়গা হয় না, তখন কয়েক পাসে merge হয় — পাসের সংখ্যা মোটামুটি ⌈log_k(N/M)⌉, তাই বড় k মানে কম পাস।

আপনি না জেনেই এটি ব্যবহার করেন: Linux-এর sort কমান্ড বড় ফাইলে ঠিক এভাবে সাময়িক ফাইলে run লিখে পরে merge করে। PostgreSQL-এ বড় ORDER BY-এর query plan দেখলে প্রায়ই লেখা থাকে “Sort Method: external merge”. আর বড় ডেটা-প্রক্রিয়াকরণের সিস্টেমগুলো (যেমন MapReduce-ধাঁচের কাঠামো) মেশিনে মেশিনে সাজানো টুকরো বানিয়ে শেষে merge করে।

৯ · Inversion গোনা — দুটি র‍্যাঙ্কিং কতটা আলাদা

একটি রান্নার প্রতিযোগিতায় দুজন বিচারক পাঁচটি পদ (A, B, C, D, E) ১ থেকে ৫ র‍্যাঙ্ক দিলেন। বিচারক ১: A B C D E. বিচারক ২: C A B E D. দুজনের মত কতটা মেলে? একটি স্বাভাবিক মাপ: কতগুলো জোড়া নিয়ে তাঁরা একমত নন। বিচারক ১-এর ক্রমে প্রতিটি পদের অবস্থান (A = 0, B = 1, …) দিয়ে বিচারক ২-এর তালিকা লিখলে পাই [2, 0, 1, 4, 3]. এখন যেসব জোড়া এখানে “উল্টো” — আগের সংখ্যা বড় — সেগুলোই মতভেদ: (2, 0), (2, 1), (4, 3) — ৩টি।

অ্যারেতে i < j অথচ a[i] > a[j] — এমন জোড়াকে বলে inversion (পর্ব ০৫-এ দেখেছেন)। সাজানো অ্যারেতে ০টি, উল্টো অ্যারেতে সর্বোচ্চ n(n − 1)/2 টি। দুটি র‍্যাঙ্কিংয়ের মধ্যে inversion-এর সংখ্যাকে বলে Kendall tau distance — পরিসংখ্যানবিদ Maurice Kendall ১৯৩৮ সালে এই ভিত্তিতে একটি rank correlation সংজ্ঞায়িত করেন। আমাদের উদাহরণে ১০টি জোড়ার ৩টিতে মতভেদ, ৭টিতে মিল; Kendall-এর τ = (৭ − ৩)/১০ = ০.৪. সংগীত বা সিনেমার অ্যাপ এমন মাপ দিয়ে দেখতে পারে আপনার পছন্দের ক্রম কার সাথে মেলে; সার্চ ইঞ্জিনের দুটি ফলাফল-তালিকাও এভাবে তুলনা করা যায়।

Brute force প্রতিটি জোড়া দেখে — Θ(n²). n = 10^৫ হলে প্রায় ৫০০ কোটি জোড়া। আরেকটি তথ্য: insertion sort ঠিক inversion-এর সংখ্যার সমান বার উপাদান সরায় (পর্ব ২০), তাই সেটিও Θ(n²) পর্যন্ত।

Merge sort দিয়ে O(n log n): প্রতিটি inversion তিন ধরনের — দুটিই বাঁ অর্ধেকে, দুটিই ডান অর্ধেকে, অথবা একটি বাঁয়ে আর একটি ডানে (cross inversion). প্রথম দুটি রিকার্শন গুনবে। আর cross inversion গোনা যায় merge করার সময়ই, বিনা খরচে: যখন ডান অংশ থেকে a[j] নেওয়া হয়, তখন বাঁ অংশে অপেক্ষায় থাকা সব উপাদান (mid − i টি) a[j]-এর চেয়ে বড় — কারণ বাঁ অংশ সাজানো আর তাদের সবচেয়ে ছোটটিই a[j]-এর চেয়ে বড় ছিল। আর এরা সবাই মূল অ্যারেতে a[j]-এর আগে ছিল (বাঁ অর্ধেক বলে)। তাই এক ধাক্কায় inv += mid - i. সমান হলে বাঁ দিক থেকে নেওয়া (<=) জরুরি — সমান জোড়া inversion নয়।

কেন সাজানোর পরও গোনা ঠিক থাকে? কারণ একটি অর্ধেকের ভেতরে উপাদানের ক্রম বদলালেও, বাঁ অর্ধেকের প্রতিটি উপাদান ডান অর্ধেকের প্রতিটির আগে — এই সত্যটি বদলায় না। cross inversion শুধু “কে কোন অর্ধেকে” আর মান দেখে, অর্ধেকের ভেতরের ক্রম দেখে না।

সময়: merge sort-এর ওপর প্রতিটি merge-ধাপে শুধু একটি যোগ — Θ(n log n), জায়গা Θ(n). এবার কোডে চালিয়ে দেখুন, সাথে O(n²) brute force দিয়ে ৫০০টি এলোমেলো অ্যারেতে যাচাই। দুই ভাষায় একই এলোমেলো সংখ্যা পেতে একটি সরল linear congruential generator (LCG) নিজে লেখা হয়েছে:

#include <iostream>
#include <vector>
using namespace std;

long long sortCount(vector<int>& a, vector<int>& buf, int lo, int hi) {
    if (hi - lo <= 1) return 0;
    int mid = lo + (hi - lo) / 2;
    long long inv = sortCount(a, buf, lo, mid) + sortCount(a, buf, mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[i] <= a[j]) buf[k++] = a[i++];
        else { inv += mid - i; buf[k++] = a[j++]; }   // a[j] is smaller than every left item still waiting
    }
    while (i < mid) buf[k++] = a[i++];
    while (j < hi)  buf[k++] = a[j++];
    for (k = lo; k < hi; ++k) a[k] = buf[k];
    return inv;
}
long long countInv(vector<int> a) {                  // by value: works on a copy
    vector<int> buf(a.size());
    return sortCount(a, buf, 0, (int)a.size());
}
long long brute(const vector<int>& a) {              // O(n^2): check every pair
    long long c = 0;
    for (size_t i = 0; i < a.size(); ++i)
        for (size_t j = i + 1; j < a.size(); ++j) c += a[i] > a[j];
    return c;
}
int main() {
    vector<int> a{5, 2, 4, 7, 1, 3, 2, 6};
    cout << "inversions = " << countInv(a) << ", brute = " << brute(a) << '\n';
    vector<int> b{2, 0, 1, 4, 3};    // judge B's order, written as positions in judge A's order
    cout << "kendall tau distance = " << countInv(b) << " of " << b.size() * (b.size() - 1) / 2 << " pairs\n";
    unsigned x = 2026; int bad = 0;
    for (int t = 0; t < 500; ++t) {
        vector<int> r(t % 30);
        for (int& v : r) { x = x * 1103515245u + 12345u; v = (x >> 16) % 10; }
        if (countInv(r) != brute(r)) ++bad;
    }
    cout << "random tests: 500, mismatches: " << bad << '\n';
}

inversions = 14, brute = 14
kendall tau distance = 3 of 10 pairs
random tests: 500, mismatches: 0

def sort_count(a, buf, lo, hi):
    if hi - lo <= 1:
        return 0
    mid = (lo + hi) // 2
    inv = sort_count(a, buf, lo, mid) + sort_count(a, buf, mid, hi)
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            buf[k] = a[i]; i += 1
        else:
            inv += mid - i                # a[j] is smaller than every left item still waiting
            buf[k] = a[j]; j += 1
        k += 1
    buf[k:hi] = a[i:mid] + a[j:hi]
    a[lo:hi] = buf[lo:hi]
    return inv

def count_inv(a):
    a = list(a)                           # work on a copy
    return sort_count(a, [0] * len(a), 0, len(a))

def brute(a):                             # O(n^2): check every pair
    return sum(a[i] > a[j] for i in range(len(a)) for j in range(i + 1, len(a)))

a = [5, 2, 4, 7, 1, 3, 2, 6]
print(f"inversions = {count_inv(a)}, brute = {brute(a)}")
b = [2, 0, 1, 4, 3]    # judge B's order, written as positions in judge A's order
print(f"kendall tau distance = {count_inv(b)} of {len(b) * (len(b) - 1) // 2} pairs")
x, bad = 2026, 0
for t in range(500):
    r = []
    for _ in range(t % 30):
        x = (x * 1103515245 + 12345) & 0xFFFFFFFF
        r.append((x >> 16) % 10)
    if count_inv(r) != brute(r):
        bad += 1
print(f"random tests: 500, mismatches: {bad}")

inversions = 14, brute = 14
kendall tau distance = 3 of 10 pairs
random tests: 500, mismatches: 0

১০ · AI-এর যুগে merge sort — সাজানো ফল মানেই সঠিক কোড নয়

“Merge sort লিখে দাও” — AI কয়েক সেকেন্ডে চলনসই কোড দেবে, আর ছোট উদাহরণে সাজানো ফলও আসবে। বিপদ সেখানেই: সাজানো ফল দেখলে মনে হয় সব ঠিক, অথচ stability ভাঙা, প্রতিটি ডাকে নতুন মেমরি বরাদ্দ, বা inversion-এর সংখ্যা int-এ উপচে পড়া — কোনোটিই ছোট উদাহরণে ধরা পড়ে না। আর complexity নিয়ে AI কখনো লেখে “merge sort O(1) জায়গায় চলে” বা “সাজানো ইনপুটে O(n)” — দুটিই সাধারণ রূপের জন্য ভুল।

Merge sort-এর কোডে AI সাধারণত যেসব ভুল করে

Merge sort-এর কোড যাচাইয়ের চেকলিস্ট

• merge-এর শর্তে <= আছে, আর কেন — stability — তা বলতে পারি
• Edge case চালিয়েছি: খালি, ১টি, ২টি, সব সমান, সাজানো, উল্টো, বিজোড় আকার
• ৮টি উপাদানের একটি অ্যারে খাতায় recursion tree এঁকে প্রতিটি merge কোডের ছাপার সাথে মিলিয়েছি
• buffer একবারই বানানো হয়েছে; প্রতিটি ডাকে নতুন মেমরি বরাদ্দ নেই
• O(n²) brute force-এর সাথে কয়েকশো এলোমেলো ছোট অ্যারেতে (অনেক সমান মানসহ) ফল মিলিয়েছি
• বড় উত্তরের (inversion) জন্য long long; n = 10^৫ উল্টো অ্যারেতে উত্তর n(n − 1)/2 এসেছে