Khi $N = 1.000.000$, $N^2 = 1.000.000.000.000$ phép tính (chạy mất vài phút), trong khi $N \log_2 N \approx 20.000.000$ phép tính (chạy dưới 0.1 giây). Sự chênh lệch này thúc đẩy sự ra đời của Merge Sort và Quick Sort.

1. Sắp xếp Trộn (Merge Sort)

• Tư duy Chia để trị:

  1. Chia: Chia đôi mảng thành 2 nửa cho đến khi mảng chỉ còn 1 phần tử.

  2. Trị: Mảng 1 phần tử coi như đã sắp xếp.

  3. Kết hợp: Trộn (Merge) hai mảng đã sắp xếp thành một mảng hoàn chỉnh ngăn nắp.

• Độ phức tạp: Thời gian $\Theta(N \log N)$ trong mọi trường hợp; Bộ nhớ phụ $O(N)$ (để tạo mảng tạm khi trộn).

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

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)


def merge(left: list, right: list) -> list:
    result = []
    i = j = 0

    # Trộn hai mảng đã sắp xếp
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

2. Sắp xếp Nhanh (Quick Sort)

• Tư duy Chia để trị:

  1. Chọn một phần tử làm Chốt (Pivot).

  2. Phân hoạch (Partition): Đưa các phần tử nhỏ hơn Pivot sang bên trái, các phần tử lớn hơn Pivot sang bên phải.

  3. Đệ quy sắp xếp hai nửa trái/phải.

• Độ phức tạp: Thời gian trung bình $O(N \log N)$; Thời gian xấu nhất $O(N^2)$ (khi chọn Pivot kém, ví dụ mảng đã sắp xếp nhưng luôn chọn phần tử cuối làm Pivot); Bộ nhớ phụ $O(\log N)$ (do Call Stack đệ quy).

BÀI TẬP CỦNG CỐ 

Bài tập 1: Phân tích Lựa chọn Thuật toán

Trong ứng dụng thực tế, hàm sắp xếp mặc định của Python (list.sort() hay sorted()) sử dụng thuật toán Timsort (kết hợp giữa Merge Sort và Insertion Sort).

Dựa vào các kiến thức trên, anh hãy giải thích lý do tại sao Timsort lại kết hợp hai thuật toán này thay vì chỉ sử dụng độc lập Merge Sort hay Quick Sort?

Bài tập 2: Thử thách Cài đặt Thuật toán (Thực hành Code)

Cho một mảng các số nguyên đã được sắp xếp tăng dần nhưng bị xoay tại một vị trí chưa biết (Rotated Sorted Array).

Ví dụ: Mảng gốc [1, 2, 3, 4, 5, 6, 7] bị xoay thành [4, 5, 6, 7, 1, 2, 3].

Viết hàm search_rotated(arr: list, target: int) -> int bằng cách biến tấu thuật toán Binary Search để tìm vị trí của target trong mảng xoay với độ phức tạp thời gian $O(\log N)$.