0

Thuật toán & CTDL #04: Merge Sort - chia để trị và nhanh gấp ~25.000 lần Bubble Sort

Với 1 triệu con số, Bubble Sort cần khoảng 500 tỷ phép so sánh. Merge Sort cần khoảng 20 triệu. Chênh nhau cỡ 25.000 lần. Không có mẹo tối ưu vi mô nào ở đây, chỉ là một chiến lược khác hẳn: chia để trị (divide and conquer). Bài này đi qua cách Merge Sort chạy, vì sao nó luôn là O(n log n), và cái giá phải trả.

Ý tưởng

Hai bước:

  1. Chia: cắt đôi mảng, rồi cắt đôi tiếp từng nửa, đến khi mỗi phần chỉ còn một phần tử. Một phần tử thì luôn được sắp.
  2. Trộn (merge): ghép hai mảng đã sắp thành một mảng đã sắp. Cách ghép rất đơn giản: so hai phần tử đứng đầu hai mảng, phần tử nào nhỏ hơn thì lấy ra trước. Một bên hết thì chép nốt bên còn lại.

Toàn bộ "trí thông minh" nằm ở bước trộn. Trộn hai mảng đã sắp có tổng m phần tử chỉ tốn tối đa m-1 lần so sánh, vì mỗi lần so sánh đưa được một phần tử vào đúng chỗ.

Chạy tay một ví dụ

Mảng trong video: [5, 2, 8, 1, 7, 3, 6, 4].

Chia (3 tầng, vì 8 = 2³):

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

Trộn ngược lên, phần đã sắp to dần: 2, rồi 4, rồi 8.

[5]+[2] -> [2, 5]        [8]+[1] -> [1, 8]
[7]+[3] -> [3, 7]        [6]+[4] -> [4, 6]
[2, 5]+[1, 8] -> [1, 2, 5, 8]
[3, 7]+[4, 6] -> [3, 4, 6, 7]
[1, 2, 5, 8]+[3, 4, 6, 7] -> [1, 2, 3, 4, 5, 6, 7, 8]

Xem kỹ lần trộn cuối: so 1 với 3, lấy 1. So 2 với 3, lấy 2. So 5 với 3, lấy 3. So 5 với 4, lấy 4. So 5 với 6, lấy 5. So 8 với 6, lấy 6. So 8 với 7, lấy 7. Bên phải hết, chép nốt 8. Tổng 7 lần so sánh.

Cả quá trình tốn 17 lần so sánh, so với 25 của Bubble Sort. Với 8 phần tử thì chênh lệch chưa ấn tượng, nhưng hãy xem phần độ phức tạp.

Code Python

def merge_sort(a):
    if len(a) <= 1:
        return list(a)
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= giữ stable: bằng nhau thì lấy bên trái trước
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])             # một bên hết, chép nốt bên kia
    out.extend(right[j:])
    return out

print(merge_sort([5, 2, 8, 1, 7, 3, 6, 4]))  # [1, 2, 3, 4, 5, 6, 7, 8]
print(merge_sort([3, 1, 2]))                 # [1, 2, 3]

Độ phức tạp

Mảng n phần tử bị chia đôi khoảng log₂ n lần. Ở mỗi tầng, tổng công việc trộn là O(n) (mỗi phần tử được chép đúng một lần). Vậy tổng là O(n log n).

  • Tốt nhất, trung bình, tệ nhất: đều O(n log n). Cách chia không phụ thuộc dữ liệu, nên không có "dữ liệu xấu" nào làm nó chậm đi. Đây là điểm mạnh lớn so với Quick Sort.
  • Bộ nhớ: O(n) cho mảng phụ khi trộn, cộng O(log n) cho stack đệ quy. Đây là cái giá phải trả.
  • Stable: có, nhờ dùng <= khi trộn.

Tính cho 1 triệu số:

  • Bubble Sort: n(n-1)/2 ≈ 5 × 10¹¹, tức ~500 tỷ.
  • Merge Sort: n log₂ n ≈ 10⁶ × 19,93 ≈ ~20 triệu (đây là cận trên, số thực tế còn thấp hơn một chút).
  • Tỉ lệ: 5 × 10¹¹ / 2 × 10⁷ ≈ 25.000 lần.

Nếu mỗi phép so sánh tốn 1 nano giây, Bubble Sort mất hơn 8 phút, còn Merge Sort mất khoảng 0,02 giây.

Khi nào dùng, khi nào không

Dùng khi:

  • Cần stable và cần đảm bảo O(n log n) trong mọi trường hợp. Ví dụ sắp xếp đơn hàng theo ngày, các đơn cùng ngày phải giữ nguyên thứ tự cũ.
  • Linked list: trộn hai danh sách liên kết chỉ cần nối lại con trỏ, không cần mảng phụ O(n). Merge Sort là lựa chọn kinh điển để sắp linked list.
  • Dữ liệu lớn hơn RAM (external sort): sắp từng khúc vừa RAM, ghi ra đĩa, rồi trộn các khúc lại. Bước trộn chỉ cần đọc tuần tự, rất hợp với đĩa.
  • Song song hóa: hai nửa độc lập, chia cho hai luồng được.

Không phải lựa chọn tốt nhất khi bộ nhớ eo hẹp (cần thêm O(n)), hoặc với mảng nhỏ (đệ quy và cấp phát tốn hơn Insertion Sort). Thực tế, Timsort của Python chính là lai giữa Merge Sort và Insertion Sort để lấy ưu điểm của cả hai.

Lỗi hay gặp

  1. Quên chép phần còn lại sau vòng while: mất phần tử.
  2. Dùng < thay vì <= khi trộn: vẫn ra mảng đúng thứ tự nhưng mất stable.
  3. Điều kiện dừng sai: viết if len(a) == 0 thì mảng 1 phần tử bị chia mãi thành [] và [x], đệ quy vô hạn.
  4. Cắt mảng quá nhiều: a[:mid] tạo bản sao mới mỗi lần. Code minh họa như trên là ổn, nhưng bản tối ưu thường truyền chỉ số lo, hi và dùng một mảng phụ dùng chung.

Câu hỏi phỏng vấn hay gặp

  • Vì sao Merge Sort luôn O(n log n)? Vì luôn chia đôi đúng giữa, không phụ thuộc giá trị phần tử.
  • Nhược điểm chính? Cần O(n) bộ nhớ phụ với mảng.
  • Sắp xếp linked list dùng thuật toán gì? Merge Sort, vì không cần truy cập ngẫu nhiên và trộn không tốn bộ nhớ phụ.
  • Đếm số nghịch thế trong mảng? Biến thể của Merge Sort: khi lấy phần tử từ nửa phải, cộng thêm số phần tử còn lại ở nửa trái. O(n log n).

Lời kết

Merge Sort là lần đầu tiên trong series ta thoát khỏi O(n²), và ý tưởng chia để trị sẽ còn quay lại nhiều lần nữa. Còn câu hỏi "Merge Sort hay Quick Sort" thì để bài sau trả lời.

Đây là bài 04/19 của series "Thuật toán & Cấu trúc dữ liệu - Giải thuật". Bản video ngắn có hoạt hình minh họa từng bước chia đôi và trộn ngược lên nằm trên page Trà Đá Tech: https://www.facebook.com/profile.php?id=61596642752252

Bạn thuộc team Merge Sort hay team Quick Sort? Hãy chia sẻ lý do trong phần bình luận.

Nếu thấy bài viết hữu ích, hãy upvote và follow để theo dõi các bài tiếp theo.

Bài tiếp theo: Quick Sort - nhanh nhất ngoài đời thực, nhưng chọn chốt tệ là rơi về O(n²)


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí