Java: Tạo mảng đã sắp xếp từ hợp nhất 2 mảng không sắp xếp

Bài toán: Cho 2 mảng chưa sắp xếp, hãy hợp nhất (merge) chúng thành một mảng mới và sắp xếp kết quả tăng dần.

Thuật toán

1. Tạo mảng kết quả có độ dài = độ dài mảng 1 + độ dài mảng 2.
2. Copy tất cả phần tử từ mảng 1 vào mảng kết quả.
3. Copy tất cả phần tử từ mảng 2 vào mảng kết quả (tiếp theo mảng 1).
4. Sắp xếp mảng kết quả bằng Arrays.sort() (Dual-Pivot Quicksort cho primitive, TimSort cho object).

Ví dụ hoàn chỉnh

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("Mảng 1: " + Arrays.toString(arr1));
        System.out.println("Mảng 2: " + Arrays.toString(arr2));
        
        // Hợp nhất
        int[] merged = mergeAndSort(arr1, arr2);
        
        System.out.println("Mảng hợp nhất đã sắp xếp: " + Arrays.toString(merged));
    }
    
    public static int[] mergeAndSort(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        int idx = 0;
        
        for (int v : a) result[idx++] = v;
        for (int v : b) result[idx++] = v;
        
        Arrays.sort(result);
        return result;
    }
}

Kết quả

Mảng 1: [50, 22, 15, 40, 65, 75]
Mảng 2: [60, 45, 10, 20, 35, 56]
Mảng hợp nhất đã sắp xếp: [10, 15, 20, 22, 35, 40, 45, 50, 56, 60, 65, 75]

Cách 2: Sử dụng Stream API (Java 8+)

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(Arrays.toString(merged));
    }
}

Cách 3: Merge thủ công như merge sort (nếu 2 mảng ĐÃ sắp xếp)

Lưu ý: Bài toán gốc là 2 mảng KHÔNG sắp xếp, nên cách này chỉ mang tính tham khảo nếu input đã sorted.

// Chỉ đúng khi arr1 và arr2 ĐÃ SẮP XẾP
public static int[] mergeSortedArrays(int[] a, int[] b) {
    int[] result = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    
    while (i < a.length && j < b.length) {
        result[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
    }
    while (i < a.length) result[k++] = a[i++];
    while (j < b.length) result[k++] = b[j++];
    
    return result; // Đã sorted, không cần Arrays.sort()
}

So sánh hiệu năng

Lưu ý

• Với mảng object (String[], Integer[]), dùng Stream.of(arr1).flatMap(Arrays::stream)... hoặc List + Collections.sort().
• Arrays.sort() sắp xếp tại chỗ (in-place), trả về void.
• Đối với mảng lớn, cân nhắc parallelSort() (Java 8+) để tận dụng đa nhân.