Merge Sort (Sắp Xếp Trộn)

Merge Sort là ví dụ kinh điển của chiến thuật Divide and Conquer (Chia để trị). Nó chia vấn đề lớn thành các vấn đề nhỏ hơn, giải quyết từng cái, rồi gộp kết quả lại.

Cơ Chế Hoạt Động

1. Divide (Chia): Chia mảng làm đôi liên tục cho đến khi mỗi mảng con chỉ còn 1 phần tử (mặc định đã sắp xếp).
2. Conquer (Trị): Trộn (Merge) hai mảng con đã sắp xếp thành một mảng lớn hơn cũng đã sắp xếp.

Minh Họa (ASCII Art)

Input:     [38, 27, 43, 3, 9, 82, 10]

Split 1:   [38, 27, 43, 3]      [9, 82, 10]
Split 2:   [38, 27]  [43, 3]    [9, 82]  [10]
Split 3:   [38] [27] [43] [3]   [9] [82] [10]

Merge 1:   [27, 38]  [3, 43]    [9, 82]  [10]
Merge 2:   [3, 27, 38, 43]      [9, 10, 82]

Final:     [3, 9, 10, 27, 38, 43, 82]

Code Implementation

Sử dụng đệ quy để chia và một hàm phụ trợ merge() để gộp.

C++

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    // Tạo mảng tạm
    vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    // Gộp hai mảng tạm vào arr
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy phần còn lại (nếu có)
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

Java

class MergeSort {
    void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; ++i) L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j];

        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }

    void sort(int arr[], int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }
}

Python

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] <= R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

🌍 HPN's Real-world Application

Bạn có biết hàm sort() (list.sort) huyền thoại của Python không dùng Merge Sort thuần túy? Nó dùng Timsort - một đứa con lai (hybrid) cực kỳ thông minh giữa Merge Sort và Insertion Sort. Tại sao? Vì dữ liệu thực tế thường có các đoạn con đã được sắp xếp sẵn (natural runs), và Timsort tận dụng điều đó để đạt hiệu năng khủng khiếp.