Thuật toán sắp xếp trộn: cách hoạt động, mã và độ phức tạp

Ý tưởng bằng lời đơn giản

Danh sách có không hoặc một phần tử thì đã sắp xếp. Với danh sách dài hơn:

1. Chia: tách danh sách thành nửa trái và nửa phải.
2. Trị: sắp xếp từng nửa bằng sắp xếp trộn.
3. Kết hợp: trộn hai nửa đã sắp xếp. So sánh phần tử đầu của mỗi nửa, chuyển phần tử nhỏ hơn sang đầu ra, lặp lại cho đến khi một nửa hết; rồi sao chép phần còn lại của nửa kia.

Toàn bộ công việc thực sự nằm ở bước trộn, và trộn hai danh sách đã sắp xếp có tổng độ dài n chỉ cần tối đa n − 1 phép so sánh.

Ví dụ minh họa từng bước

Sắp xếp [38, 27, 43, 3, 9, 82, 10].

Lần trộn cuối so sánh các phần tử đầu: 27 so với 3 lấy 3, 27 so với 9 lấy 9, 27 so với 10 lấy 10, 27 so với 82 lấy 27, 38 so với 82 lấy 38, 43 so với 82 lấy 43, rồi sao chép 82. Sáu phép so sánh cho bảy phần tử.

Cài đặt bằng Python

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= takes from left on ties: stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])            # one of these is empty
    out.extend(right[j:])
    return out
def merge_sort(items):
    """Return a new sorted list."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([]))                           # []

Phiên bản từ trên xuống này rõ ràng nhưng sao chép các lát cắt. Phiên bản từ dưới lên tránh hoàn toàn đệ quy: trộn các đoạn độ rộng 1, rồi 2, rồi 4, và cứ thế.

def merge_sort_bottom_up(items):
    a = list(items)
    width = 1
    while width < len(a):
        for lo in range(0, len(a), 2 * width):
            mid, hi = lo + width, lo + 2 * width
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        width *= 2
    return a

Phiên bản từ dưới lên tái sử dụng merge ở trên. Thư viện chuẩn cũng có heapq.merge, trộn lười biếng (lazy) số lượng bất kỳ iterable đã sắp xếp.

Độ phức tạp thời gian và không gian

Hệ thức truy hồi là T(n) = 2T(n/2) + O(n). Mỗi mức của cây đệ quy làm tổng cộng O(n) công việc và có khoảng log₂ n mức, nên tổng là O(n log n). Với một triệu phần tử, đó là khoảng 20 mức.

So sánh sắp xếp trộn với các thuật toán khác

Sắp xếp trộn ổn định vì phép trộn lấy từ nửa trái khi hai phần tử bằng nhau, nên các phần tử bằng nhau giữ nguyên thứ tự. So với sắp xếp nhanh, nó đảm bảo trường hợp xấu nhất O(n log n) nhưng cần O(n) bộ nhớ phụ và thường di chuyển dữ liệu nhiều hơn trên mảng. So với sắp xếp vun đống, nó ổn định và truy cập bộ nhớ tuần tự, thân thiện với bộ nhớ đệm và đĩa.

Biến thể và lỗi thường gặp

• Natural merge sort phát hiện các đoạn đã sắp xếp sẵn và trộn chúng, cho O(n) trên đầu vào đã sắp xếp. Timsort là bản natural merge sort được tinh chỉnh, dùng sắp xếp chèn nhị phân cho các đoạn ngắn.
• Chuyển sang sắp xếp chèn cho các danh sách con nhỏ (ví dụ dưới khoảng 10 đến 30 phần tử) để giảm chi phí phụ.
• Trên danh sách liên kết, sắp xếp trộn không cần bộ đệm phụ: việc trộn chỉ nối lại các nút, nên đây là lựa chọn thông thường để sắp xếp danh sách liên kết.
• Sắp xếp trộn ngoài (external merge sort) sắp xếp từng khối vừa bộ nhớ, ghi ra đĩa, rồi thực hiện trộn k đường. Cơ sở dữ liệu và công cụ như sort của GNU dùng ý tưởng này cho tệp lớn.
• Đếm nghịch thế: trong lúc trộn, mỗi khi một phần tử được lấy từ nửa phải, nó nhỏ hơn mọi phần tử còn lại của nửa trái.

Khi nào nên dùng sắp xếp trộn

Chọn sắp xếp trộn khi cần sắp xếp ổn định với thời gian O(n log n) được đảm bảo, khi sắp xếp danh sách liên kết, hoặc khi dữ liệu quá lớn so với bộ nhớ. Trong Python, chỉ cần gọi sorted() hoặc list.sort(): chúng cài đặt Timsort, một biến thể của sắp xếp trộn, nên bạn đã có sẵn các tính chất này. Tự viết sắp xếp trộn là bài phỏng vấn kinh điển, thường mở rộng sang đếm nghịch thế hoặc trộn k danh sách đã sắp xếp.