Thuật toán Merge Sort là gì? Giải thích dễ hiểu kèm demo trực quan

Merge Sort có độ phức tạp O(n log n) ổn định, hoạt động tốt ngay cả với dữ liệu lớn và đặc biệt luôn giữ tính stable.

Merge Sort giải bài toán gì?

• Cho một mảng các phần tử.
• Cần sắp xếp mảng đó theo thứ tự tăng dần hoặc giảm dần.

Merge Sort làm điều đó bằng cách chia mảng liên tục cho đến khi mỗi phần chỉ còn 1 phần tử, rồi ghép lại chúng theo đúng thứ tự.

Ý tưởng chính của Merge Sort

1. Chia mảng làm 2 phần bằng nhau.
2. Sắp xếp từng phần bằng chính Merge Sort (đệ quy).
3. Trộn hai phần đã sắp xếp lại thành một mảng hoàn chỉnh.

Ví dụ minh họa

Sắp xếp mảng:

[5, 3, 8, 4, 2, 7]

Quá trình diễn ra như sau:

• Chia: [5,3,8] + [4,2,7]
• Chia tiếp: [5] + [3,8], v.v.
• Trộn: [3,8] → trộn với 5 → [3,5,8]
• Tiếp tục đến khi có mảng cuối cùng.

Demo Merge Sort bằng JavaScript

Demo dưới đây hiển thị trực quan:

• Quá trình chia mảng.
• So sánh từng phần tử khi trộn.
• Trộn lại theo đúng thứ tự.
• Log từng bước giúp dễ quan sát.

Phân tích đoạn code Merge Sort

1. Ghi lại từng bước chia – trộn

function mergeSortWithSteps(arr) {
    var steps = [];

    function mergeSort(a) {
        if (a.length <= 1) return a;

        var mid = Math.floor(a.length / 2);
        var left = a.slice(0, mid);
        var right = a.slice(mid);

        steps.push({ type: "split", left: left.slice(), right: right.slice() });

        var sortedLeft = mergeSort(left);
        var sortedRight = mergeSort(right);

        return merge(sortedLeft, sortedRight);
    }

    function merge(left, right) {
        var result = [];
        var i = 0, j = 0;

        while (i < left.length && j < right.length) {
            steps.push({
                type: "compare",
                leftValue: left[i],
                rightValue: right[j],
                left: left.slice(),
                right: right.slice()
            });

            if (left[i] <= right[j]) {
                result.push(left[i]);
                i++;
            } else {
                result.push(right[j]);
                j++;
            }

            steps.push({
                type: "merged",
                current: result.slice()
            });
        }

        while (i < left.length) {
            result.push(left[i]);
            i++;
            steps.push({ type: "merged", current: result.slice() });
        }

        while (j < right.length) {
            result.push(right[j]);
            j++;
            steps.push({ type: "merged", current: result.slice() });
        }

        steps.push({ type: "merge_done", array: result.slice() });

        return result;
    }

    var sorted = mergeSort(arr);
    return { steps: steps, sorted: sorted };
}

2. Hiển thị mảng theo từng trạng thái

function renderMergeArray(container, arr, highlight) {
    container.innerHTML = "";
    arr.forEach(function(value, index) {
        var div = document.createElement("div");
        div.className = "merge-cell";

        if (highlight != null && highlight.includes(value)) {
            div.classList.add("merge-active");
        }

        div.textContent = value;
        container.appendChild(div);
    });
}

3. Chạy animation từng bước

function playMergeSteps(steps, sortedArray) {
    var index = 0;
    mergeLog.innerHTML = "";
    mergeResult.textContent = "Đang chạy thuật toán...";

    function next() {
        if (index >= steps.length) {
            renderMergeArray(mergeArray, sortedArray, null);
            mergeResult.innerHTML =
                "Mảng đã được sắp xếp: <strong>[" + sortedArray.join(", ") + "]</strong>";
            return;
        }

        var step = steps[index];
        var msg = "";
        var highlight = null;

        if (step.type === "split") {
            msg =
                "Chia mảng thành 2 phần: [" +
                step.left.join(", ") +
                "] và [" +
                step.right.join(", ") +
                "].";
        } else if (step.type === "compare") {
            msg =
                "So sánh " +
                step.leftValue +
                " và " +
                step.rightValue +
                ".";
            highlight = [step.leftValue, step.rightValue];
        } else if (step.type === "merged") {
            msg = "Ghép dần: [" + step.current.join(", ") + "]";
        } else if (step.type === "merge_done") {
            msg =
                "Kết thúc trộn: [" +
                step.array.join(", ") +
                "]";
        }

        renderMergeArray(mergeArray, step.current || step.array || [], highlight);

        var p = document.createElement("p");
        p.innerHTML = msg;
        mergeLog.appendChild(p);
        mergeLog.scrollTop = mergeLog.scrollHeight;

        index++;
        setTimeout(next, 700);
    }

    next();
}

Khi nào dùng Merge Sort?

• Khi dữ liệu lớn, cần độ ổn định.
• Khi cần thuật toán stable (giữ nguyên thứ tự bằng giá trị bằng nhau).
• Khi muốn tránh worst-case như Quick Sort.

Kết luận

Merge Sort là thuật toán chia–trị kinh điển, rất mạnh với dữ liệu lớn và dễ biểu diễn bằng animation chia – trộn. Demo trực quan giúp bạn thấy rõ cách thuật toán cắt mảng và ghép lại theo đúng thứ tự.