Insertion Sort — Sắp xếp chèn

Khi Python gọi sorted() hoặc Java chạy Arrays.sort(), bước cuối cùng trước khi trả kết quả không phải Merge Sort hay Quick Sort — mà là Insertion Sort. Timsort, thuật toán sắp xếp mặc định của cả hai ngôn ngữ, sử dụng Insertion Sort để xử lý các đoạn con nhỏ (run) có độ dài dưới 64 phần tử. Lý do đơn giản: không thuật toán O(n log n) nào đánh bại được Insertion Sort ở quy mô nhỏ.

Đây là thuật toán sắp xếp duy nhất hội tụ cả ba đặc tính hiếm gặp: adaptive (tự thích nghi — chạy O(n) trên dữ liệu gần sắp xếp), online (sắp xếp ngay khi dữ liệu đến mà không cần biết trước toàn bộ), và stable (giữ nguyên thứ tự tương đối của các phần tử bằng nhau). Ba đặc tính này biến nó thành lựa chọn production thực sự, không chỉ là bài tập nhập môn.

Nếu bạn nghĩ Insertion Sort chỉ là "thuật toán cơ bản để dạy trên lớp", bài viết này sẽ thay đổi góc nhìn đó.

Bức tranh tư duy

Hình dung bạn đang chơi bài tây (poker). Mỗi lần rút một lá bài mới từ bộ bài úp, bạn không xáo lại toàn bộ tay — bạn quét mắt từ phải sang trái qua các lá đang cầm, tìm đúng vị trí, rồi chèn lá mới vào đó.

Tay hiện tại:  [3] [7] [J] [K]     ← đã sắp xếp
Rút lá mới:    [9]

Quét từ phải:  K > 9 → dời phải
               J > 9 → dời phải
               7 < 9 → DỪNG, chèn 9 vào sau 7

Kết quả:       [3] [7] [9] [J] [K]

Đó chính xác là Insertion Sort. Phần tay bài bên trái luôn được sắp xếp, và mỗi lá mới chỉ cần tìm đúng vị trí để chèn vào. Càng nhiều lá đã đúng chỗ sẵn (dữ liệu gần sắp xếp), bạn càng ít phải dịch chuyển — đây là nguồn gốc tính adaptive của thuật toán.

Điểm analogy bị breakdown: khi chơi bài thật, bạn "nhìn" được toàn bộ tay bài cùng lúc (giống binary search). Insertion Sort cơ bản quét tuần tự — nhưng biến thể Binary Insertion Sort khắc phục đúng điểm này.

Cốt lõi kỹ thuật

Cơ chế hoạt động

Insertion Sort chia mảng thành hai vùng logic:

• Vùng đã sắp xếp: từ index 0 đến i-1
• Phần tử cần chèn: arr[i] (gọi là key)

Với mỗi key, thuật toán quét ngược từ i-1 về 0, dịch các phần tử lớn hơn key sang phải một vị trí, rồi đặt key vào chỗ trống.

Mảng:   [5, 2, 4, 6, 1, 3]

i=1: key=2  → dời 5 sang phải        → [2, 5, 4, 6, 1, 3]
i=2: key=4  → dời 5 sang phải        → [2, 4, 5, 6, 1, 3]
i=3: key=6  → 6 > 5, không dời       → [2, 4, 5, 6, 1, 3]
i=4: key=1  → dời 6,5,4,2 sang phải  → [1, 2, 4, 5, 6, 3]
i=5: key=3  → dời 6,5,4 sang phải    → [1, 2, 3, 4, 5, 6]

Ba đặc tính production

Adaptive — Số phép so sánh tỷ lệ thuận với số nghịch thế (inversion) trong mảng. Mảng đã sắp xếp có 0 nghịch thế → O(n). Mảng gần sắp xếp (vài phần tử bị lệch) → gần O(n).

Online — Không cần biết trước kích thước dữ liệu. Phần tử mới đến bất kỳ lúc nào đều có thể chèn ngay vào vùng đã sắp xếp. Đặc tính này lý tưởng cho streaming data.

Stable — Phần tử bằng nhau giữ nguyên thứ tự ban đầu, vì vòng lặp dừng khi gặp phần tử ≤ key (dùng > thay vì >= trong điều kiện so sánh).

Triển khai chuẩn — Polyglot

C++

void insertionSort(std::vector<int>& arr) {
    int n = static_cast<int>(arr.size());
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

Python

def insertion_sort(arr: list[int]) -> None:
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Java

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Go

func insertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

Sentinel Optimization

Kỹ thuật sentinel loại bỏ kiểm tra j >= 0 trong vòng lặp bằng cách đặt phần tử nhỏ nhất ở đầu mảng. Mỗi lần so sánh tiết kiệm một phép kiểm tra biên — hiệu quả đáng kể khi n lớn.

// Đưa phần tử min về vị trí arr[0] làm sentinel
for (int i = 1; i < n; ++i)
    if (arr[i] < arr[0]) std::swap(arr[i], arr[0]);

// Vòng lặp không cần kiểm tra j >= 0
for (int i = 2; i < n; ++i) {
    int key = arr[i];
    int j = i - 1;
    while (arr[j] > key) {  // sentinel đảm bảo dừng tự nhiên
        arr[j + 1] = arr[j];
        --j;
    }
    arr[j + 1] = key;
}

Binary Insertion Sort

Thay vì quét tuần tự để tìm vị trí chèn, dùng binary search trên vùng đã sắp xếp. Giảm số phép so sánh từ O(n²) xuống O(n log n), nhưng số phép dịch chuyển vẫn O(n²) vì phải shift phần tử trong mảng.

from bisect import insort

def binary_insertion_sort(arr: list[int]) -> None:
    for i in range(1, len(arr)):
        key = arr[i]
        # bisect tìm vị trí chèn bằng binary search
        pos = bisect_left(arr, key, 0, i)
        # Dịch các phần tử từ pos đến i-1 sang phải
        for j in range(i, pos, -1):
            arr[j] = arr[j - 1]
        arr[pos] = key

Khi nào dùng Binary Insertion Sort?

Khi chi phí so sánh cao (ví dụ: sắp xếp chuỗi dài, object phức tạp) nhưng chi phí dịch chuyển thấp (mảng nhỏ). Đây chính xác là lý do Timsort dùng Binary Insertion Sort cho các run ngắn.

Thực chiến

Tình huống 1: Timsort — Sắp xếp run ngắn

Bối cảnh: CPython, OpenJDK, Rust std::sort đều dùng Timsort. Khi chia mảng thành các run (đoạn đã sắp xếp tự nhiên), những run có kích thước dưới minrun (thường 32–64) được mở rộng bằng Insertion Sort.

Tại sao không dùng Merge Sort từ đầu? Với n < 64, overhead đệ quy và chi phí cấp phát bộ nhớ tạm của Merge Sort cao hơn hẳn so với số phép so sánh tiết kiệm được. Insertion Sort hoạt động in-place, không cần bộ nhớ phụ, và tận dụng cache CPU cực tốt nhờ truy cập tuần tự.

# Mô phỏng đoạn Insertion Sort trong Timsort
MIN_RUN = 32

def timsort_insertion(arr: list[int], left: int, right: int) -> None:
    """Sắp xếp arr[left..right] bằng Insertion Sort."""
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Tình huống 2: Streaming data — Sắp xếp khi dữ liệu đến

Bối cảnh: Server nhận event log từ nhiều nguồn, mỗi event có timestamp. Dữ liệu đến gần như theo thứ tự (chỉ lệch vài vị trí do network latency).

Mục tiêu: Duy trì danh sách event đã sắp xếp theo thời gian thực.

Insertion Sort là lựa chọn tự nhiên: mỗi event mới chỉ cần dịch vài vị trí (O(1) amortized cho dữ liệu gần sắp xếp), không cần rebuild toàn bộ cấu trúc dữ liệu.

class SortedEventBuffer:
    def __init__(self, max_size: int = 1000):
        self.events: list[dict] = []
        self.max_size = max_size

    def insert(self, event: dict) -> None:
        """Chèn event vào đúng vị trí theo timestamp."""
        ts = event["timestamp"]
        i = len(self.events) - 1
        self.events.append(event)
        # Insertion sort: quét ngược từ cuối
        while i >= 0 and self.events[i]["timestamp"] > ts:
            self.events[i + 1] = self.events[i]
            i -= 1
        self.events[i + 1] = event
        if len(self.events) > self.max_size:
            self.events.pop(0)

Phân tích: Nếu dữ liệu lệch tối đa k vị trí, mỗi lần chèn tốn O(k) — không phụ thuộc kích thước buffer.

Sai lầm điển hình

❌ Sai lầm 1: Dùng Insertion Sort cho mảng lớn ngẫu nhiên

Vấn đề: Chọn Insertion Sort để sắp xếp 100.000 phần tử ngẫu nhiên.

# SAI: O(n²) trên dữ liệu ngẫu nhiên — cực chậm
data = [random.randint(0, 10**6) for _ in range(100_000)]
insertion_sort(data)  # ~10 tỷ phép so sánh

Tại sao sai: Với n = 100.000 phần tử ngẫu nhiên, trung bình có ~n²/4 = 2.5 tỷ nghịch thế. Insertion Sort xử lý mỗi nghịch thế bằng đúng một phép swap, nên tổng thời gian là O(n²). Trong khi đó, Merge Sort chỉ cần ~n log n ≈ 1.7 triệu phép so sánh.

# ĐÚNG: Dùng thuật toán O(n log n) cho dữ liệu lớn
data.sort()  # Timsort — tự động hybrid

❌ Sai lầm 2: Không tận dụng tính adaptive

Vấn đề: Dùng Quick Sort cho mảng gần sắp xếp (ví dụ: cập nhật bảng xếp hạng khi chỉ vài vị trí thay đổi).

# SAI: Quick Sort chạy O(n log n) bất kể mảng gần sắp xếp
sorted_leaderboard = sorted(leaderboard)  # overhead không cần thiết

Tại sao sai: Insertion Sort chạy O(n + d) với d là số nghịch thế. Nếu chỉ 5 người chơi đổi hạng trong bảng 10.000 người, d ≈ 10 → gần O(n). Quick Sort vẫn tốn O(n log n) ≈ 130.000 phép so sánh.

# ĐÚNG: Insertion Sort cho dữ liệu gần sắp xếp
def update_leaderboard(board: list[int]) -> None:
    insertion_sort(board)  # O(n + d) với d rất nhỏ

❌ Sai lầm 3: Off-by-one trong vòng lặp

Vấn đề: Bắt đầu vòng ngoài từ i = 0 thay vì i = 1.

# SAI: i = 0 gây so sánh thừa hoặc lỗi logic
for i in range(0, len(arr)):
    key = arr[i]
    j = i - 1  # j = -1 khi i = 0, vòng while không chạy nhưng gây nhầm lẫn

Tại sao sai: Phần tử đầu tiên (i = 0) mặc định đã tạo thành mảng con 1 phần tử — luôn được sắp xếp. Bắt đầu từ 0 không gây lỗi runtime nhưng tốn một vòng lặp vô nghĩa và gây nhầm lẫn khi đọc code.

# ĐÚNG: Bắt đầu từ i = 1
for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1

❌ Sai lầm 4: Dùng >= thay vì > — phá vỡ tính stable

Vấn đề: Điều kiện so sánh dùng >= khiến các phần tử bằng nhau bị hoán đổi thứ tự.

# SAI: >= phá vỡ stability
while j >= 0 and arr[j] >= key:  # phần tử bằng key cũng bị dời
    arr[j + 1] = arr[j]
    j -= 1

Tại sao sai: Khi sắp xếp theo nhiều tiêu chí (sort lần 1 theo tên, sort lần 2 theo điểm), mất stability đồng nghĩa kết quả sort lần 1 bị phá. Đây là bug khó phát hiện trong production vì output "trông có vẻ đúng" nhưng thứ tự tương đối sai.

# ĐÚNG: Chỉ dời khi strictly greater than
while j >= 0 and arr[j] > key:
    arr[j + 1] = arr[j]
    j -= 1

Under the Hood

Hiệu năng

Trường hợp	Time Complexity	Số phép so sánh	Ghi chú
Best (đã sắp xếp)	O(n)	n - 1	Mỗi phần tử chỉ so sánh 1 lần
Average (ngẫu nhiên)	O(n²)	~n²/4	Trung bình n²/4 nghịch thế
Worst (sắp xếp ngược)	O(n²)	n(n-1)/2	Mọi cặp đều là nghịch thế
Space	O(1)	—	In-place, chỉ dùng biến key và j

Mối quan hệ với Inversion Count

Thời gian chạy của Insertion Sort = Θ(n + d) với d là tổng số nghịch thế (inversion). Một nghịch thế là cặp (i, j) mà i < j nhưng arr[i] > arr[j].

• Mảng đã sắp xếp: d = 0 → O(n)
• Mảng ngẫu nhiên: d ≈ n(n-1)/4 → O(n²)
• Mảng sắp ngược: d = n(n-1)/2 → O(n²)

Công thức này giải thích chính xác tại sao Insertion Sort nhanh trên dữ liệu gần sắp xếp — không phải cảm tính mà là toán học.

Tại sao Insertion Sort thắng Merge Sort khi n < 64

Timsort (CPython) đặt ngưỡng MIN_MERGE = 64. Dưới ngưỡng này, Insertion Sort nhanh hơn vì:

1. Không có overhead đệ quy: Merge Sort cần log₂(n) tầng đệ quy, mỗi tầng có chi phí call stack.
2. Không cần bộ nhớ phụ: Merge Sort cần mảng tạm O(n) — cấp phát và giải phóng tốn thời gian.
3. Cache-friendly: Insertion Sort truy cập phần tử liền kề nhau trong bộ nhớ (spatial locality). Merge Sort nhảy qua lại giữa hai mảng con.
4. Hằng số ẩn nhỏ: Mỗi bước của Insertion Sort chỉ là compare + shift — hai thao tác đơn giản. Merge Sort cần compare + copy to temp + copy back — ba thao tác.

Trade-offs

Tiêu chí	Insertion Sort	Merge Sort	Quick Sort
Best case	O(n) ✅	O(n log n)	O(n log n)
Worst case	O(n²) ❌	O(n log n) ✅	O(n²)
Space	O(1) ✅	O(n)	O(log n)
Stable	Có ✅	Có ✅	Không
Adaptive	Có ✅	Không	Không
Online	Có ✅	Không	Không
n < 64	Nhanh nhất	Chậm hơn	Chậm hơn
n > 10.000	Chậm	Nhanh	Nhanh

Checklist ghi nhớ

✅ Checklist triển khai

Cơ chế thuật toán

• [ ] Insertion Sort chia mảng thành vùng đã sắp xếp (trái) và chưa sắp xếp (phải)
• [ ] Mỗi bước lấy phần tử đầu tiên của vùng chưa sắp xếp, quét ngược và chèn vào đúng vị trí
• [ ] Vòng ngoài bắt đầu từ i = 1 (không phải 0) vì phần tử đầu tiên mặc định đã sắp xếp

Đặc tính quan trọng

• [ ] Adaptive: O(n + d) với d là số nghịch thế — O(n) cho dữ liệu gần sắp xếp
• [ ] Online: có thể sắp xếp ngay khi dữ liệu đến, không cần biết trước toàn bộ
• [ ] Stable: dùng > (không phải >=) trong điều kiện so sánh để giữ thứ tự tương đối
• [ ] In-place: chỉ dùng O(1) bộ nhớ phụ

Ứng dụng thực tế

• [ ] Timsort dùng Insertion Sort cho run nhỏ hơn 64 phần tử — đây là ứng dụng production phổ biến nhất
• [ ] Ưu tiên Insertion Sort khi dữ liệu gần sắp xếp hoặc n nhỏ (< 50-64 phần tử)
• [ ] Sentinel optimization giảm một phép kiểm tra biên mỗi vòng lặp — hiệu quả cho tight loops

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

Bài 1: Đếm số phép dịch chuyển — Foundation

Đề bài: Cho mảng arr gồm n số nguyên. Đếm tổng số phép dịch chuyển (shift) mà Insertion Sort thực hiện để sắp xếp mảng tăng dần. Đây chính là số nghịch thế (inversion count) của mảng.

Input: arr = [2, 1, 3, 1, 2]Output: 4

💡 Gợi ý

• Mỗi phép arr[j + 1] = arr[j] trong vòng while là một phép dịch chuyển
• Thêm biến đếm vào đúng vị trí trong Insertion Sort
• Kết quả chính là tổng số nghịch thế của mảng

✅ Lời giải

def count_shifts(arr: list[int]) -> int:
    shifts = 0
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
            shifts += 1
        arr[j + 1] = key
    return shifts

Phân tích: Time O(n²) worst case, Space O(1). Với mảng lớn cần đếm inversion, dùng Merge Sort biến thể để đạt O(n log n).

Bài 2: Insertion Sort trên Linked List — Intermediate

Đề bài: Triển khai Insertion Sort trên singly linked list. Không được chuyển sang mảng rồi sort — phải thao tác trực tiếp trên node.

Ràng buộc: Tận dụng đặc tính của linked list: chèn phần tử không cần dịch chuyển (O(1) insert), nhưng tìm vị trí chèn phải quét tuần tự (O(n) search).

💡 Gợi ý

• Tạo một dummy head cho danh sách kết quả đã sắp xếp
• Với mỗi node từ danh sách gốc, tìm vị trí chèn trong danh sách kết quả
• Thao tác con trỏ: tách node ra khỏi danh sách gốc, gắn vào vị trí đúng

✅ Lời giải

class ListNode:
    def __init__(self, val: int = 0, next: 'ListNode | None' = None):
        self.val = val
        self.next = next

def insertion_sort_list(head: ListNode | None) -> ListNode | None:
    dummy = ListNode(0)
    current = head
    while current:
        next_node = current.next
        # Tìm vị trí chèn trong danh sách đã sắp xếp
        prev = dummy
        while prev.next and prev.next.val < current.val:
            prev = prev.next
        # Chèn current vào sau prev
        current.next = prev.next
        prev.next = current
        current = next_node
    return dummy.next

Phân tích: Time O(n²), Space O(1). Trên linked list, Insertion Sort không cần dịch chuyển phần tử — chỉ thay đổi con trỏ. Đây là LeetCode #147.

🧠 Quiz

Insertion Sort chạy O(n) trong trường hợp nào?

• [ ] A. Mảng có tất cả phần tử giống nhau
• [ ] B. Mảng đã sắp xếp tăng dần
• [x] C. Cả A và B
• [ ] D. Mảng sắp xếp giảm dần Giải thích: Khi mảng đã sắp xếp tăng dần (B), mỗi phần tử chỉ cần 1 phép so sánh → tổng n-1 phép → O(n). Khi tất cả phần tử giống nhau (A), điều kiện arr[j] > key luôn false → vòng while không chạy → cũng O(n). Mảng giảm dần (D) là worst case O(n²) vì mọi cặp đều tạo nghịch thế.

🎬 Bubble Sort Visualizer

64

34

25

12

22

11

90

45

67

30

Chưa sắp xếp Đang so sánh Đã sắp xếp

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• ← Bubble Sort — Thuật toán sắp xếp đơn giản hơn, so sánh tư duy "swap liên tục" vs "chèn đúng vị trí"
• → Merge Sort — Thuật toán O(n log n) đầu tiên, dùng Divide and Conquer
• Selection Sort — So sánh trực tiếp: cùng O(n²) nhưng Selection Sort không adaptive và không stable
• Timsort — Hybrid sort dùng Insertion Sort cho run ngắn — ứng dụng production thực tế
• Độ phức tạp thuật toán — Nền tảng phân tích Big O cần thiết để hiểu adaptive complexity

Từ khóa glossary: insertion sort, sắp xếp chèn, nghịch thế, inversion, adaptive sort, online sort, stable sort, sentinel, binary insertion sort

Tìm kiếm liên quan: sắp xếp chèn, insertion sort là gì, thuật toán sắp xếp cơ bản, sắp xếp ổn định, timsort insertion sort