Chuyển tới nội dung chính

Merge sort (Sắp xếp trộn)

Bạn sẽ học được gì

Merge sort là thuật toán sắp xếp đầu tiên đưa ta vượt khỏi O(n^2). Bằng chiến lược chia để trị (divide and conquer) — cắt đôi mảng, sắp từng nửa, rồi trộn (merge) hai nửa đã sắp — nó đạt O(n log n) trong mọi trường hợp. Đổi lại, nó cần O(n) bộ nhớ phụ.

1. Trực quan: trộn hai chồng bài đã sắp​

Tưởng tượng hai người bạn, mỗi người cầm một chồng bài đã sắp tăng dần. Nhiệm vụ của bạn: gộp chúng thành một chồng lớn cũng đã sắp. Cách làm rất tự nhiên — bạn chỉ nhìn lá trên cùng của hai chồng, lấy lá nhỏ hơn đặt xuống, rồi lặp lại. Vì mỗi chồng đã sắp sẵn, bạn không bao giờ phải nhìn lại phía sau.

Đó là phép merge. Merge sort = áp dụng ý tưởng này một cách đệ quy: cứ cắt đôi cho tới khi mỗi mảnh chỉ còn một phần tử (hiển nhiên đã sắp), rồi trộn ngược lên.

            [5 3 8 1 9 2]
            /            \
       [5 3 8]          [1 9 2]          <- chia
       /     \          /     \
    [5]   [3 8]      [1]   [9 2]
           / \              / \
         [3] [8]          [9] [2]
           \ /              \ /
          [3 8]            [2 9]          <- tron len
         /                      \
     [3 5 8]                  [1 2 9]
            \                /
           [1 2 3 5 8 9]                  <- ket qua

2. Ý tưởng cốt lõi: chia, trị, trộn​

Ba bước kinh điển của chia để trị (xem lại bài 1.3.4):

  1. Chia (divide): cắt mảng làm đôi tại giữa.
  2. Trị (conquer): sắp xếp đệ quy mỗi nửa.
  3. Trộn (merge): gộp hai nửa đã sắp thành một mảng đã sắp — đây là phần "cơ bắp".
Thuộc tínhGiá trịVì sao
Thời gianO(n log n)log n tầng chia, mỗi tầng trộn tốn O(n)
Bộ nhớO(n)cần mảng phụ để trộn
Ổn địnhCóphần tử bằng nhau giữ nguyên thứ tự gốc

3. Chạy debug: trộn [3, 8] với [1, 9]​

Trái tim của merge sort là phép trộn. Bước qua để thấy ta lấy lá nhỏ hơn ở mỗi bước.

🐞 Merge [3, 8] và [1, 9]Bước 1/5
1L = [3, 8]
2R = [1, 9]
3out = []
4# so 3 vs 1 -> lay 1
5# so 3 vs 9 -> lay 3
6# so 8 vs 9 -> lay 8
7# R con 9 -> lay 9
Biến tại bước này
L[3, 8]
R[1, 9]
out[]
👉 Hai mảng đã sắp, kết quả rỗng.

4. Code chạy được​

Đang tải trình chạy code…

5. Phân tích: vì sao O(n log n)?​

  • Số tầng chia là log n: cứ cắt đôi mãi, từ n về 1 mất khoảng log2(n) lần.
  • Mỗi tầng tốn O(n): ở mỗi tầng, tổng số phần tử cần trộn vẫn là n.
  • Nhân lại: log n tầng nhân n công mỗi tầng → O(n log n). Quan trọng: con số này không đổi dù dữ liệu tốt hay xấu — merge sort rất ổn định về hiệu năng.
  • Đánh đổi bộ nhớ: phép trộn cần mảng phụ → O(n). Đây là điểm yếu so với quick sort (sắp tại chỗ). Khi RAM eo hẹp, đó là điều phải cân nhắc.
  • Bẫy thường gặp: dùng < thay vì <= khi so ở bước trộn — nó vẫn sắp đúng nhưng mất tính ổn định (đảo thứ tự các phần tử bằng nhau).

6. Mẫu nhận diện​

  • Cần đảm bảo O(n log n) kể cả trường hợp xấu nhất → merge sort (quick sort có thể tệ O(n^2)).
  • Cần sắp xếp ổn định (giữ thứ tự phần tử bằng nhau) → merge sort là lựa chọn kinh điển.
  • Sắp xếp danh sách liên kết → merge sort hợp hơn quick sort (không cần truy cập ngẫu nhiên).
  • Bài toán cho thấy cấu trúc "giải nửa rồi gộp" → nghĩ tới chia để trị + merge.

7. 🎮 Trò chơi: Hiểu merge sort​

🎮 Merge sort & chia để trịCâu 1/4· Điểm 0· 🔥 0

Cắt đôi, sắp từng nửa, rồi trộn. O(n log n) mọi trường hợp, ổn định, tốn O(n) bộ nhớ.

Độ phức tạp thời gian của merge sort trong TRƯỜNG HỢP XẤU NHẤT là?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Merge sort thuộc nhóm chiến lược thuật toán nào?
2. Vì sao merge sort cho O(n log n) trong MỌI trường hợp?
3. Để giữ tính ổn định khi trộn, ta so sánh thế nào?

9. Hoàn thành​

…

☑️ Tiếp theo: 3.1.3 — Quick sort (chia để trị quanh pivot, nhanh trong thực tế).