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

মার্জ সোর্ট একটি ডিভাইড-এন্ড-কঙ্কোয়ার (বিভাগ কর এবং জয় কর) সোর্টিং টেকনিক। পুরো ডেটাসেটকে ছোট ছোট অংশে ভাগ করে, সেগুলোকে সর্টেড অর্ডারে মার্জ করে বড় করে তৈরি করা হয়। এটি ওয়ার্স্ট কেসেও ভালো পারফর্ম করে কারণ এর ওয়ার্স্ট কেস টাইম কমপ্লেক্সিটি কম।

মার্জ সোর্টের জটিলতা

• টাইম কমপ্লেক্সিটি: সব কেসের জন্য O(n log n)
• স্পেস কমপ্লেক্সিটি: O(n)

ইনপুট এবং আউটপুট

Input: The unsorted list: 14 20 78 98 20 45
Output: Array before Sorting: 14 20 78 98 20 45
        Array after Sorting: 14 20 20 45 78 98

অ্যালগরিদম

merge(array, left, middle, right)

Begin
    nLeft := middle - left + 1
    nRight := right - middle
    leftArr এবং rightArr অ্যারের সাইজ nLeft এবং nRight
    বাম এবং ডান সাব-অ্যারে ভরুন
    i := 0, j := 0, k := left
    while i < nLeft AND j < nRight do
        if leftArr[i] <= rightArr[j] then array[k] = leftArr[i], i++
        else array[k] = rightArr[j], j++
        k++
    done
    বাকি এলিমেন্টগুলো কপি করুন
End

mergeSort(array, left, right)

Begin
    if left < right then
        mid := left + (right - left) / 2
        mergeSort(array, left, mid)
        mergeSort(array, mid+1, right)
        merge(array, left, mid, right)
End

C++ উদাহরণ

#include <iostream>
using namespace std;

void display(int *array, int size) {
    for(int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

void merge(int *array, int l, int m, int r) {
    int nl = m - l + 1, nr = r - m;
    int larr[nl], rarr[nr];
    for(int i = 0; i < nl; i++) larr[i] = array[l + i];
    for(int j = 0; j < nr; j++) rarr[j] = array[m + 1 + j];
    int i = 0, j = 0, k = l;
    while(i < nl && j < nr) {
        if(larr[i] <= rarr[j]) array[k++] = larr[i++];
        else array[k++] = rarr[j++];
    }
    while(i < nl) array[k++] = larr[i++];
    while(j < nr) array[k++] = rarr[j++];
}

void mergeSort(int *array, int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;
        mergeSort(array, l, m);
        mergeSort(array, m + 1, r);
        merge(array, l, m, r);
    }
}

int main() {
    int n; cout << "Enter the number of elements: "; cin >> n;
    int arr[n];
    cout << "Enter elements:" << endl;
    for(int i = 0; i < n; i++) cin >> arr[i];
    cout << "Array before Sorting: "; display(arr, n);
    mergeSort(arr, 0, n-1);
    cout << "Array after Sorting: "; display(arr, n);
}

আউটপুট

Enter the number of elements: 6
Enter elements: 14 20 78 98 20 45
Array before Sorting: 14 20 78 98 20 45
Array after Sorting: 14 20 20 45 78 98