Java: สร้าง Sorted Merged Array จากสอง Unsorted Arrays

โปรแกรมสร้าง sorted merged array จากสอง unsorted arrays โดยรวม array ทั้งสองแล้ว sort ผลลัพธ์

อัลกอริทึม

1. สร้าง array ใหม่ขนาด = ขนาด array1 + array2
2. คัดลอก elements จาก array1 และ array2 ลง array ใหม่
3. เรียงลำดับ array ใหม่ด้วย Arrays.sort()

Time Complexity: O((n+m) log(n+m)) | Space: O(n+m)

ตัวอย่างโค้ด

import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        int[] arr1 = {50, 22, 15, 40, 65, 75};
        int[] arr2 = {60, 45, 10, 20, 35, 56};

        System.out.println("1st Array = " + Arrays.toString(arr1));
        System.out.println("2nd Array = " + Arrays.toString(arr2));

        int count1 = arr1.length;
        int count2 = arr2.length;
        int[] resArr = new int[count1 + count2];

        int i = 0, j = 0, k = 0;

        // Copy arr1
        while (i < arr1.length) {
            resArr[k] = arr1[i];
            i++;
            k++;
        }

        // Copy arr2
        while (j < arr2.length) {
            resArr[k] = arr2[j];
            j++;
            k++;
        }

        // Sort merged array
        Arrays.sort(resArr);

        System.out.println("Sorted Merged Array = " + Arrays.toString(resArr));
    }
}

Output

1st Array = [50, 22, 15, 40, 65, 75]
2nd Array = [60, 45, 10, 20, 35, 56]
Sorted Merged Array = [10, 15, 20, 22, 35, 40, 45, 50, 56, 60, 65, 75]

วิธีทางเลือก: ใช้ Java 8+ Streams

import java.util.Arrays;
import java.util.stream.IntStream;

public class StreamDemo {
    public static void main(String[] args) {
        int[] arr1 = {50, 22, 15, 40, 65, 75};
        int[] arr2 = {60, 45, 10, 20, 35, 56};

        int[] merged = IntStream.concat(
            Arrays.stream(arr1),
            Arrays.stream(arr2)
        ).sorted().toArray();

        System.out.println("Merged (Stream): " + Arrays.toString(merged));
    }
}

วิธีทางเลือก: Merge แบบ Sorted Arrays (Two-pointer) - O(n+m)

ถ้า array ทั้งสอง sorted อยู่แล้ว ใช้ two-pointer technique ไม่ต้อง sort ใหม่:

public class MergeSortedArrays {
    public static int[] mergeSorted(int[] arr1, int[] arr2) {
        int[] result = new int[arr1.length + arr2.length];
        int i = 0, j = 0, k = 0;

        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] <= arr2[j]) {
                result[k++] = arr1[i++];
            } else {
                result[k++] = arr2[j++];
            }
        }

        while (i < arr1.length) result[k++] = arr1[i++];
        while (j < arr2.length) result[k++] = arr2[j++];

        return result;
    }

    public static void main(String[] args) {
        int[] a = {10, 20, 30, 40};
        int[] b = {15, 25, 35, 45, 55};
        
        int[] merged = mergeSorted(a, b);
        System.out.println(Arrays.toString(merged));
        // [10, 15, 20, 25, 30, 35, 40, 45, 55]
    }
}

Generic Version (สำหรับ Object Arrays)

import java.util.Arrays;
import java.util.Comparator;

public class GenericMerge {
    @SafeVarargs
    public static  T[] mergeAndSort(T[]... arrays) {
        // Calculate total length
        int totalLength = 0;
        for (T[] arr : arrays) totalLength += arr.length;

        // Create result array (ต้องใช้ reflection เพราะ generic array creation)
        @SuppressWarnings("unchecked")
        T[] result = (T[]) java.lang.reflect.Array.newInstance(
            arrays[0].getClass().getComponentType(), totalLength);

        // Copy all arrays
        int pos = 0;
        for (T[] arr : arrays) {
            System.arraycopy(arr, 0, result, pos, arr.length);
            pos += arr.length;
        }

        // Sort
        Arrays.sort(result);
        return result;
    }

    public static void main(String[] args) {
        String[] a = {"delta", "alpha"};
        String[] b = {"epsilon", "beta", "gamma"};
        
        String[] merged = mergeAndSort(a, b);
        System.out.println(Arrays.toString(merged));
        // [alpha, beta, delta, epsilon, gamma]
    }
}

สรุปการเลือกวิธี