Giới thiệu

Sắp xếp hợp nhất (Merge Sort) là thuật toán sắp xếp dựa trên nguyên lý chia để trị và đệ quy. Bài viết này trình bày chi tiết về cách triển khai và tối ưu thuật toán này.

Nguyên lý hoạt động

Thuật toán hoạt động theo 2 bước chính:

1. Chia mảng: Chia mảng thành hai nửa và thực hiện sắp xếp từng nửa.
2. Hợp nhất: Kết hợp hai mảng đã được sắp xếp thành một mảng duy nhất.

Triển khai hàm hợp nhất

private static <E extends Comparable<E>> void combine(E[] data, int start, int mid, int end) {
    E[] temp = Arrays.copyOfRange(data, start, end + 1);
    int left = start, right = mid + 1;
    
    for (int current = start; current <= end; current++) {
        if (left > mid) {
            data[current] = temp[right - start];
            right++;
        } else if (right > end) {
            data[current] = temp[left - start];
            left++;
        } else if (temp[left - start].compareTo(temp[right - start]) <= 0) {
            data[current] = temp[left - start];
            left++;
        } else {
            data[current] = temp[right - start];
            right++;
        }
    }
}

Triển khai đệ quy

public static <E extends Comparable<E>> void sort(E[] data) {
    sort(data, 0, data.length - 1);
}

private static <E extends Comparable<E>> void sort(E[] data, int start, int end) {
    if (start >= end) return;
    int mid = start + (end - start) / 2;
    sort(data, start, mid);
    sort(data, mid + 1, end);
    combine(data, start, mid, end);
}

Tối ưu hóa

• Phân tích trạng thái mảng: Nếu phần tử giữa nhỏ hơn phần tử kế tiếp, bỏ qua bước hợp nhất.
• Tối ưu bộ nhớ: Tạo mảng tạm thời trước khi gọi đệ quy.

Ví dụ: Đếm cặp nghịch đảo

Sử dụng nguyên lý sắp xếp hợp nhất để đếm số cặp nghịch đảo trong mảng.

class Solution {
    private int count;

    public int countInversePairs(int[] numbers) {
        int[] temp = new int[numbers.length];
        sort(numbers, 0, numbers.length - 1, temp);
        return count;
    }

    private void sort(int[] data, int start, int end, int[] temp) {
        if (start >= end) return;
        int mid = start + (end - start) / 2;
        sort(data, start, mid, temp);
        sort(data, mid + 1, end, temp);
        
        if (data[mid] > data[mid + 1])
            merge(data, start, mid, end, temp);
    }

    private void merge(int[] data, int start, int mid, int end, int[] temp) {
        System.arraycopy(data, start, temp, start, end - start + 1);
        int left = start, right = mid + 1;

        for (int current = start; current <= end; current++) {
            if (left > mid) {
                data[current] = temp[right];
                right++;
            } else if (right > end) {
                data[current] = temp[left];
                left++;
            } else if (temp[left] <= temp[right]) {
                data[current] = temp[left];
                left++;
            } else {
                count += mid - left + 1;
                data[current] = temp[right];
                right++;
            }
        }
    }
}