การรวม Array สองอัน (Merge Arrays) ในภาษา C

เงื่อนไข

• Array ทั้งสองต้อง จัดเรียงแล้ว (Sorted)
• ผลลัพธ์จะเป็น Sorted Array เดียว

อัลกอริทึม Merge (Two Pointers)

i = 0, j = 0, k = 0;
while(i < n1 && j < n2) {
    if(a[i] <= b[j])
        c[k++] = a[i++];
    else
        c[k++] = b[j++];
}

// Copy เหลือ (ถ้ามี)
while(i < n1) c[k++] = a[i++];
while(j < n2) c[k++] = b[j++];

ตัวอย่างโปรแกรมครบถ้วน (รวม Sort + Merge)

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

#define MAX 10

void sort(int arr[], int n) {
    // Simple Bubble Sort
    for(int i = 0; i < n-1; i++)
        for(int j = 0; j < n-1-i; j++)
            if(arr[j] > arr[j+1]) {
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
}

void merge(int a[], int n, int b[], int m, int c[]) {
    int i = 0, j = 0, k = 0;
    
    while(i < n && j < m) {
        if(a[i] <= b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }
    while(i < n) c[k++] = a[i++];
    while(j < m) c[k++] = b[j++];
}

void printArray(int arr[], int n, const char *name) {
    printf("%s: ", name);
    for(int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int a[MAX], b[MAX], c[2*MAX];
    int n, m;
    
    printf("Enter size of Array 1: ");
    scanf("%d", &n);
    printf("Enter %d elements: ", n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    printf("Enter size of Array 2: ");
    scanf("%d", &m);
    printf("Enter %d elements: ", m);
    for(int i = 0; i < m; i++) scanf("%d", &b[i]);
    
    // Sort both arrays first
    sort(a, n);
    sort(b, m);
    
    printArray(a, n, "Array 1 (sorted)");
    printArray(b, m, "Array 2 (sorted)");
    
    // Merge
    merge(a, n, b, m, c);
    
    printArray(c, n + m, "Merged Array");
    
    return 0;
}

ผลลัพธ์

Enter size of Array 1: 4
Enter 4 elements: 1 2 3 4
Enter size of Array 2: 3
Enter 3 elements: 6 8 3
Array 1 (sorted): 1 2 3 4
Array 2 (sorted): 3 6 8
Merged Array: 1 2 3 3 4 6 8

Merge แบบไม่ Sort (Concatenate)

ถ้าไม่ต้องการ Sorted แค่ต่อกัน:

void concat(int a[], int n, int b[], int m, int c[]) {
    for(int i = 0; i < n; i++) c[i] = a[i];
    for(int i = 0; i < m; i++) c[n + i] = b[i];
}

การใช้งานจริง

• Merge Sort - ขั้นตอน Merge เป็นหัวใจของ Merge Sort
• External Sorting - รวมไฟล์ที่ Sort แล้ว
• Database Join - Merge Join Algorithm
• Stream Processing - รวมข้อมูลจากหลายแหล่ง

ความซับซ้อน

• Time: O(n + m) - Linear
• Space: O(n + m) - ต้องมี Array ตัวรับ
• In-Place Merge: ซับซ้อนกว่า ต้องการ O(1) Space แต่ช้ากว่า