Sắp xếp trộn

Khái niệm

Sắp xếp trộn (merge sort) áp dụng chiến lược chia để trị (divide and conquer):

Chia — Chia đôi dãy thành hai nửa.
Trị — Đệ quy sắp xếp mỗi nửa.
Trộn — Kết hợp hai nửa đã sắp xếp thành một dãy hoàn chỉnh.

Độ phức tạp thời gian: O(n log n) — ở mọi trường hợp
Độ phức tạp không gian: O(n) — cần mảng phụ để trộn
Ổn định: Có

Sơ đồ chia và trộn

graph TD; A["[5,2,4,6,1,3]"] --> B["[5,2,4]"]; A --> C["[6,1,3]"]; B --> D["[5,2]"]; B --> E["[4]"]; C --> F["[6,1]"]; C --> G["[3]"]; D --> H["[5]"]; D --> I["[2]"]; F --> J["[6]"]; F --> K["[1]"]; H --> L["[2,5]"]; I --> L; L --> M["[2,4,5]"]; E --> M; J --> N["[1,6]"]; K --> N; N --> O["[1,3,6]"]; G --> O; M --> P["[1,2,3,4,5,6]"]; O --> P;

Cài đặt

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # Sắp xếp nửa trái
    right = merge_sort(arr[mid:])   # Sắp xếp nửa phải
    return merge(left, right)       # Trộn hai nửa

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= giữ tính ổn định
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])         # Thêm phần còn lại
    result.extend(right[j:])
    return result

data = [5, 2, 4, 6, 1, 3]
print(merge_sort(data))  # [1, 2, 3, 4, 5, 6]

Bài tập luyện tập

Dễ — Trộn hai dãy đã sắp xếp

Hàm merge là trái tim của merge sort. Thực hành viết hàm trộn hai dãy sắp xếp độc lập.

def tron_hai_day(a, b):
    """Trộn hai dãy đã sắp xếp tăng dần thành một dãy sắp xếp."""
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

print(tron_hai_day([1, 3, 5], [2, 4, 6]))     # [1, 2, 3, 4, 5, 6]
print(tron_hai_day([1, 2, 3], [4, 5, 6]))     # [1, 2, 3, 4, 5, 6]
print(tron_hai_day([], [1, 2, 3]))            # [1, 2, 3]

Trung bình — Đếm cặp nghịch thế với merge sort

Mỗi lần chọn phần tử từ nửa phải (right[j]) trong khi nửa trái còn lại (len(left) - i) phần tử → tất cả các phần tử còn lại của nửa trái đều lớn hơn right[j] → tạo (len(left) - i) cặp nghịch thế. Đây là thuật toán O(n log n) để đếm cặp nghịch thế.

def merge_dem_nghich_the(arr):
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, cnt_l = merge_dem_nghich_the(arr[:mid])
    right, cnt_r = merge_dem_nghich_the(arr[mid:])

    merged = []
    cnt = cnt_l + cnt_r
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            cnt += len(left) - i    # Tất cả phần tử còn lại của left > right[j]
            merged.append(right[j]); j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, cnt

_, count = merge_dem_nghich_the([2, 4, 1, 3, 5])
print(count)   # 3

_, count = merge_dem_nghich_the([5, 4, 3, 2, 1])
print(count)   # 10 (dãy ngược hoàn toàn)

Khó — Sắp xếp xen kẽ (Merge K sorted lists)

Trộn k danh sách đã sắp xếp thành một danh sách duy nhất. Dùng kỹ thuật merge từng cặp.

import heapq

def tron_k_danh_sach(lists):
    """Trộn k danh sách đã sắp xếp thành một. O(n log k)."""
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))  # (giá trị, list_idx, elem_idx)

    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))

    return result

lists = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(tron_k_danh_sach(lists))   # [1, 2, 3, 4, 5, 6, 7, 8, 9]

lists2 = [[1, 3], [2], [4, 5, 6]]
print(tron_k_danh_sach(lists2))  # [1, 2, 3, 4, 5, 6]

Kết luận

Merge sort là thuật toán ổn định O(n log n) bất kể đầu vào. Nó là nền tảng cho nhiều thuật toán nâng cao như đếm nghịch thế, External Sort (sắp xếp dữ liệu lớn hơn RAM). Tiếp theo hãy học Sắp xếp nhanh — thường nhanh hơn trong thực tế dù cùng độ phức tạp về mặt ký hiệu.

Trong series này: