সি ভাষায় দুটি অ্যারে মার্জ (Merge) করা

দুটি সর্টেড অ্যারে মার্জ করা (Merge Two Sorted Arrays)

দুটি ইতিমধ্যে সর্টেড অ্যারেকে একসাথে মার্জ করে একটি বড় সর্টেড অ্যারে তৈরি করা হয়। এটি মার্জ সর্ট অ্যালগরিদমের কোর স্টেপ।

অ্যালগরিদম (Two-Pointer Technique)

1. তিনটি ইন্ডেক্স: i (merged), j (arr1), k (arr2) — সব ০ থেকে শুরু।
2. যখন j < n1 এবং k < n2:
   • যদি arr1[j] <= arr2[k] → merged[i++] = arr1[j++]
   • অন্যথায় → merged[i++] = arr2[k++]
3. বাকি এলিমেন্টগুলো কপি করুন।

সি প্রোগ্রাম

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

// সর্টিং হেল্পার (বাবল সর্ট)
void sort(int a[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-1-i; j++)
            if (a[j] > a[j+1]) {
                int t = a[j]; a[j] = a[j+1]; a[j+1] = t;
            }
}

int main() {
    int a[10], b[10], c[20];
    int n, m, o, i, j, k;

    printf("Enter size of Array 1: ");
    scanf("%d", &n);
    printf("Enter size of Array 2: ");
    scanf("%d", &m);

    o = n + m;

    printf("Enter %d elements for Array 1: ", n);
    for (i = 0; i < n; i++) scanf("%d", &a[i]);

    printf("Enter %d elements for Array 2: ", m);
    for (i = 0; i < m; i++) scanf("%d", &b[i]);

    // সর্ট করুন (ইনপুট যদি সর্টেড না থাকে)
    sort(a, n);
    sort(b, m);

    printf("\nSorted Array 1: ");
    for (i = 0; i < n; i++) printf("%d ", a[i]);

    printf("\nSorted Array 2: ");
    for (i = 0; i < m; i++) printf("%d ", b[i]);

    // মার্জ
    i = j = k = 0;
    while (j < n && k < m) {
        if (a[j] <= b[k]) c[i++] = a[j++];
        else c[i++] = b[k++];
    }
    while (j < n) c[i++] = a[j++];
    while (k < m) c[i++] = b[k++];

    printf("\n\nMerged Array: ");
    for (i = 0; i < o; i++) printf("%d ", c[i]);
    printf("\n");

    return 0;
}

আউটপুট

Enter size of Array 1: 4
Enter size of Array 2: 3
Enter 4 elements for Array 1: 1 2 3 4
Enter 3 elements for Array 2: 6 8 3

Sorted Array 1: 1 2 3 4
Sorted Array 2: 3 6 8

Merged Array: 1 2 3 3 4 6 8

টাইম ও স্পেস কমপ্লেক্সিটি

• টাইম: O(n + m) (লিনিয়ার)
• স্পেস: O(n + m) (এক্সট্রা অ্যারে)

নোট

• ইনপুট অ্যারে দুটো সর্টেড থাকলে সর্টিং স্টেপ বাদ দিয়ে সরাসরি মার্জ করা যায়।
• ইন-প্লেস মার্জ (এক্সট্রা স্পেস ছাড়া) সম্ভব কিন্তু জটিল।
• এই লজিক মার্জ সর্টের ভিত্তি।