মডিউল ২৩_৩ঃ How Divide Works in Merge Sort

আমরা বলেছিলাম যে merge sort Divide and Conquere স্ট্র্যাটেজিতে কাজ করে। Conquere পার্টটা আমরা অলরেডি দেখেছি। এবার দেখবো Divide কিভাবে কাজ করে।

আমরা মেইন এ্যারেকে ভাঙ্গতে থাকবো। প্রথমে দুইটা পয়েন্টার সেট করবো l ও r । যদি l<r হয় তাহলে তাদের আবার ভাঙ্গবো। এবার r = (l+r)/2| এভাবে করে ততক্ষন ভাঙ্গতে থাকবো যতক্ষন পর্যন্ত l>= r হচ্ছে না।

তাহলে এই এ্যারে এর ক্ষেত্রে ব্যাপারটা হবে,

১ ৩ ৫ ৭ ৯ ৮

১ ৩ ৫

১

৩ ৫

৩

৫

৭ ৮ ৯

৭

৮ ৯

৮

৯

সম্পূর্ণ কোডঃ

// Some code
#include<bits/stdc++.h>
using namespace std;
void divide(int a[],int l, int r)
{
    for(int i=l;i<=r;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    if(l<r)
    {
        int mid=(l+r)/2;
        divide(a,l,mid);
        divide(a,mid+1,r);
    }
}
int main()
{
    int n; 
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    divide(a,0,n-1);
    return 0;
}