মার্জ সর্ট হচ্ছে Divide and Conquer অ্যালগরিদম। বিভিন্ন ধরণের অ্যালগরিদমিক প্যারাডাইম রয়েছে, যেমন Greedy, Dynamic Programming ইত্যাদি। Divide and Conquer হচ্ছে একটা প্যারাডাইম। এটি একটি সমস্যাকে সমাধান করতে নিচের ধাপ গুলো অনুসরণ করেঃ

1. Divide: সমস্যাটাকে ছোট ছোট অংশে ভাগ করে ফেলে।
2. Conquer: ভাগ করার পর ছোট ছোট অংশ গুলোকে সমাধান করে। সাধারণত রিকার্শন ব্যবহার করে।
3. Combine: ছোট ছোট সমাধান গুলোকে আবার একত্র করে মূল সমাধান রিটার্ণ করে।

এর আগে বাবল সর্ট এবং ইনসার্শন সর্ট সম্পর্কে জেনেছি আমরা। দুইটাই বলতে গেলে অনেক সহজ। কিন্তু তাদের টাইমকমপ্লেক্সিটি অনেক বেশি O(n²)। মার্জ সর্ট একটু কঠিন কিন্তু টাইম কমপ্লেক্সিটি কম O(n Log n)। মার্জ সর্ট সম্পর্কে জানার আগে জানতে হবে কিভাবে রিকার্শন কাজ করে।

মার্জ সর্টের তিনটা প্রধান অংশ। একটা হচ্ছে আমরা যে লিস্টটাকে সর্ট করব, তাকে ছোট ছোট অংশে ভাগ করে ফেলা। এরপর ঐ ছোট ছোট অংশ গুলোতে সাজানো। এবং সাজানো অংশ গুলোকে আবার একত্র করা। Divide, Conquer, Combine।

মার্জ সর্ট সম্পর্কে লেখার আগে কিভাবে দুইটা সর্টেড বা সাজানো লিস্টকে মার্জ করা হয়, তা সম্পর্কে জেনে নেই। নিচের দুইটা লিস্ট দেখি। একটা ডান পাশে, একটা বাম পাশে। প্রতিটাতে ৩টি করে সংখ্যা রয়েছে। আমরা যদে লক্ষ্য করি, তাহলে দেখব লিস্ট দুইটাই সর্টেড অবস্থায় রয়েছে। এখন এই দুইটা সর্টেড লিস্টকে আমরা মার্জ করব।

মার্জ করা মানে হচ্ছে দুইটা লিস্টকে একত্র করে একটা লিস্টে যোগ করব। মার্জ এমব ভাবে করতে হবে, যেন আমাদের ফাইনাল লিস্টটি সর্টেড অবস্থায় থাকে।

এখন যেহেতু দুইটা লিস্টই সর্টেড অবস্থায় রয়েছে, আমরা নতুন লিস্ট তৈরি করার সময়  লিস্ট দুইটির প্রথম দুইটি সংখ্যার মধ্যে তুলনা করব। এরপর যেটা ছোট হবে, ঐটাই আমাদের নতুন লিস্টের প্রথমে রাখব।

এখন 2 এবং 1 এর মধ্যে 1 ছোট। তাই আমরা 1 কে আমাদের নতুন লিস্টের প্রথমে রাখব।

এরপর আবার আমাদের দুইটি লিস্টের প্রথম দুইটা সংখ্যার মধ্যে তুলনা করব। এখানে রয়েছে 2 এবং 5। এদের মধ্যে 2 ছোট। তাই আমরা আমাদের নতুন লিস্টে 2 রাখব।

এপর আবার আমাদের দুইটি লিস্টের প্রথম দুইটি সংখ্যার মধ্যে তুলনা করে দেখব 4 ছোট, তাই 4 কে নতুন লিস্টে রাখব।

এভাবে বাকি গুলো নতুন লিস্টে যুক্ত করার পর আমরা একটি সর্টেড লিস্ট পেয়ে যাবোঃ

এভাবেই মার্জ কাজ করে। মার্জ সর্টের দুইটা প্রধান অংশ হচ্ছে যে লিস্টটাকে সর্ট করতে হবে, তাকে ছোট ছোট অংশে ভাগ করে ফেলা। তখন প্রতিটা অংশে একটা করে মাত্র সংখ্যা থাকবে। এরপর পরবর্তীতে ঐ ছোট অংশ গুলোকে মার্জ করা। মার্জ সর্ট কিভাবে কাজ করে, তার ভিজুয়াল চিত্রঃ

সোর্সঃ Wikipedia
অ্যালগরিদমটা এভাবে লেখা যায়ঃ

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array

   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

সি প্রোগ্রামিং এ ইমপ্লিমেন্টেশনঃ

#include<stdlib.h>
#include<stdio.h>

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    /* create temp arrays */
    int L[n1], R[n2];


    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];


    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }


    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}


void mergeSort(int arr[], int low, int high)
{
    if (low < high)
    {

        int m = low+(high-low)/2;

        // Sort first and second halves
        mergeSort(arr, low, m);
        mergeSort(arr, m+1, high);

        merge(arr, low, m, high);
    }
}

int main()

{   int i;
    int arr[] = {2, 4, 8, 5, 1, 6};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    mergeSort(arr, 0, arr_size - 1);

    for (i=0; i < arr_size; i++)
        printf("%d ", arr[i]);

    return 0;
}

এই সম্পর্কিত আরো কিছু লেখাঃ

• অ্যালগরিদম, কমপ্লেক্সিটি এনালাইসিস ও নোটেশন
• অ্যালগরিদমঃ ইনসার্শন সর্ট ও সি প্রোগ্রামিং এ ইমপ্লিমেন্টেশন
• অ্যালগরিদমঃ লিনিয়ার সার্চ
• অ্যালগরিদমঃ বাবল সর্ট
• ব্রেডথ ফার্স্ট সার্চ অ্যালগরিদম – Breadth-first search
• ডেপথ ফার্স্ট সার্চ অ্যালগরিদম – Depth-First Search
• রিকার্শন/ Recursion , রিকার্সিভ অ্যালগরিদম, রিকার্সিভ ফাংশন ও সি প্রোগ্রামিং এ প্রয়োগ
• লিঙ্কড লিস্ট / Linked list সম্পর্কে ধারণা এবং সি প্রোগ্রামিং এ ইমপ্লিমেন্টেশন
• গ্রাফ থিওরি, গ্রাফের রিপ্রেজেন্টেশন এবং ইমপ্লিমেন্টেশন