Sắp Xếp Hợp Nhất (Merge Sort) trong C++: Hành Trình Khám Phá

🌌 Sự Chia Rẽ và Đại Thống Nhất: Huyền Thoại Sắp Xếp Hợp Nhất

"Điều gì nguyên vẹn phải...
— Bài Ca của Người Thống Nhất

Giới Thiệu

Sắp xếp hợp nhất (Merge Sort) là một thuật toán sắp xếp mạnh mẽ, sử dụng phương pháp chia và chinh phục. Trong bài viết này, chúng ta sẽ khám phá quy trình hoạt động của thuật toán này thông qua huyền thoại về sự chia rẽ và đại thống nhất. Bằng cách sử dụng ví dụ thực tế và mã nguồn, bạn sẽ hiểu rõ cách thức hoạt động của Merge Sort, cũng như cách áp dụng nó trong các tình huống thực tế.

📜 Cuộn Cuốn Chia Rẽ

#include <iostream>
#include <vector>
using namespace std;

Khi bắt đầu, các nhà viết sử chuẩn bị cuộn giấy (iostream) và lưới (vector) để chia thế giới ra thành nhiều mảnh và sau đó kết nối lại với nhau.

⚔️ Bùa Phép Thống Nhất

void merge(vector<int>& arr, int left, int mid, int right) {

Bùa phép đầu tiên được gọi là merge. Nó có sức mạnh để thống nhất hai phần lại với nhau, và chỉ trong sự thống nhất đó mới có thể hiện thực hóa trật tự.

    int n1 = mid - left + 1;
    int n2 = right - mid;

Oracle nhìn vào thế giới và thấy nó bị chia thành hai. Phần bên trái chứa n1 chiến binh, phần bên phải chứa n2. Hai trại đã hình thành, chờ đợi phán quyết.

    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

Những chiến binh được đưa vào hai cuộn giấy: L và R. Mỗi chiến binh ghi nhớ nguồn gốc của mình và đứng chờ đợi để được thống nhất.

🌌 Đại Thống Nhất

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

Oracle bắt đầu quá trình thống nhất. Từ mỗi bên, chiến binh nhỏ nhất được chọn. Nếu chiến binh bên trái nhỏ hơn hoặc bằng, anh ta sẽ bước vào hàng. Ngược lại, chiến binh bên phải sẽ chiếm chỗ. Từng bước, họ đi vào, lấp đầy mảng với trật tự.

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

Khi một trại đã hết quân, những chiến binh còn lại của trại khác tiến lên mà không bị cản trở. Tất cả đều tìm thấy vị trí của mình trong hàng ngũ mới, có trật tự. Thao tác thống nhất hoàn tất.

🏹 Nghi Lễ Chia Rẽ

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

Bùa phép thứ hai được gọi là mergeSort. Sức mạnh của nó chính là sự chia rẽ.

Oracle nhìn vào hàng ngũ. Nếu nhiều hơn một chiến binh đứng trong hàng, bà chia họ ra. Điểm giữa được chọn — chia vương quốc thành trái và phải.

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

Sự chia rẽ không chỉ diễn ra một lần mà là nhiều lần. Mỗi nửa bị chia nhỏ hơn nữa, cho đến khi chỉ còn lại những chiến binh đơn lẻ.

Một chiến binh đơn lẻ không cần sắp xếp. Một mình, anh ta đã đủ trật tự.

        merge(arr, left, mid, right);
    }
}

Nhưng khi tất cả đã bị chia rẽ, Oracle bắt đầu hành trình ngược lại. Sự thống nhất bắt đầu. Hai nửa trở thành một, sau đó lớn hơn, cho đến khi cuối cùng toàn bộ vương quốc được thống nhất — không trong hỗn loạn, mà trong trật tự tăng dần hoàn hảo.

🎺 Thử Thách Tám

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

Một ngày nọ, bảy chiến binh đứng trong hàng: 38, 27, 43, 3, 9, 82, 10. Họ mạnh mẽ nhưng hỗn loạn.

    mergeSort(arr, 0, arr.size() - 1);

Oracle nâng tay. Sự chia rẽ bắt đầu. Mỗi chiến binh bị tách ra khỏi đồng đội cho đến khi anh ta đứng một mình.

Sau đó, từ từ, kiên nhẫn, sự thống nhất diễn ra. Khi các nửa trở thành một, những chiến binh bước vào vị trí định trước của họ.

👏 Lời Gọi của Sứ Giả

    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
}

Cuối cùng, Sứ giả bước đi trong hàng. Từng chiến binh được gọi tên. Tên của họ không vang lên trong hỗn loạn, mà trong trật tự — chiến binh nhỏ nhất trước, lớn nhất sau.

Đám đông reo hò. Lời tiên tri đã được thực hiện. Vương quốc đã được thống nhất, hoàn hảo.

🧠 Ký Ức của Sự Chia Rẽ

• mergeSort — nghi lễ chia rẽ, phá vỡ thế giới cho đến khi chỉ còn những chiến binh đơn lẻ.
• merge — đại thống nhất, kết hợp các nửa bằng cách chọn chiến binh nhỏ nhất mỗi lần.
• vòng lặp while — sự di chuyển của những người sống sót vào hàng cuối cùng.

Vì vậy, Merge Sort được nhớ đến như là Huyền Thoại về Sự Chia Rẽ và Thống Nhất, nơi sự phân chia mang lại hòa hợp.