Sau bốn bài về các thuật toán sắp xếp O(n log n) "nhanh", insertion sort nghe như một bước lùi: nó O(n²), thứ mà bài big-O dạy ta là chậm hơn hẳn theo bậc. Ai cũng biết O(n²) thua O(n log n). Nhưng "ai cũng biết" là chỗ để đo lại, và insertion sort là ví dụ đẹp nhất trong cả sê-ri cho thấy một nhãn độ phức tạp có thể sai về thực tế tới mức nào. Bài này đo hai tình huống mà thuật toán "chậm" này thắng cả những thuật toán "nhanh" — và giải thích vì sao mọi thư viện sắp xếp nghiêm túc đều bí mật dùng nó.
Insertion sort: chèn từng phần tử vào chỗ đúng
Insertion sort làm đúng như tên: duyệt mảng từ trái sang, và với mỗi phần tử, chèn nó vào đúng vị trí trong phần đã sắp nằm bên trái — bằng cách dịch những phần tử lớn hơn sang phải để lấy chỗ. Giống cách bạn sắp một nắm bài trên tay: rút từng lá, đẩy nó vào đúng khe. Trường hợp trung bình và xấu, mỗi phần tử phải dịch trung bình nửa mảng, nên tổng công là O(n²) — và đó là con số mọi người nhớ, rồi gạt insertion sort sang một bên như một thuật toán "để dạy, không để dùng".
Nhưng con số O(n²) đó là một tóm tắt tiệm cận: nó mô tả điều gì xảy ra khi n tiến ra vô cùng, trên dữ liệu xấu nhất. Nó cố tình bỏ qua hai thứ mà thực tế lại rất hay gặp: khi n nhỏ, và khi dữ liệu gần như đã sắp. Tôi đo cả hai, và ở cả hai insertion sort thắng.
Đo thứ nhất: ở mảng nhỏ, O(n²) thắng O(n log n)
Big-O nói quicksort (O(n log n)) nhanh hơn insertion sort (O(n²)). Điều đó chỉ đúng khi n đủ lớn để log n thắng hằng số. Ở n nhỏ, các hằng số bị giấu trong ký hiệu O mới là thứ quyết định — và hằng số của insertion sort cực bé: không đệ quy, không chọn pivot, chỉ một vòng lặp gọn nằm hoàn toàn trong cache. Tôi sắp rất nhiều mảng nhỏ và đo thời gian trung bình mỗi phần tử:
n (cỡ mảng) insertion quicksort merge nhanh nhất
4 3,4 ns 4,4 ns 6,9 ns insertion
16 6,0 ns 10,0 ns 11,9 ns insertion
64 9,6 ns 14,8 ns 18,4 ns insertion
128 13,8 ns 17,1 ns 21,7 ns insertion
256 22,9 ns 19,3 ns 24,4 ns quicksort
Có một điểm crossover rõ ràng: insertion sort nhanh nhất cho tới quanh 128 phần tử, và chỉ từ 256 quicksort mới vượt lên. Ở những mảng nhỏ này, cái O(n²) chẳng những không hại mà còn thắng, vì n² với n=16 chỉ là 256 phép, trong khi quicksort trả giá cho đệ quy, chọn pivot, và những lần gọi hàm mà insertion sort không có. Đây không phải chi tiết học thuật — nó là lý do kỹ thuật rất thực dụng ở phần sau.
Đo thứ hai: insertion sort là adaptive
Tình huống thứ hai còn ấn tượng hơn. Insertion sort adaptive: nó làm ít việc hẳn khi dữ liệu đã gần có thứ tự, vì mỗi phần tử chỉ phải dịch một vài chỗ (hoặc không chỗ nào). Tôi đo cùng một insertion sort trên ba loại đầu vào 200 nghìn phần tử:
đầu vào (n=200k) insertion quicksort
ngẫu nhiên 2477 ms (O(n²)) 8,2 ms
đã sắp 0,09 ms (O(n)!) 1,7 ms
gần sắp (1%) 0,11 ms (~O(n)) 1,6 ms
Cùng một thuật toán, ba số phận trải trên năm bậc độ lớn. Trên dữ liệu ngẫu nhiên, insertion sort là 2.477 mili giây — đúng thảm họa O(n²), chậm hơn quicksort 300 lần. Nhưng trên mảng đã sắp, nó chỉ 0,09 mili giây — nhanh hơn chính nó trên dữ liệu ngẫu nhiên khoảng 27 nghìn lần, và nhanh hơn cả quicksort 19 lần. Vì trên dữ liệu đã sắp, insertion sort chỉ đi một vòng, mỗi phần tử so một lần rồi thấy đã đúng chỗ, không dịch gì — đúng n phép, O(n) thuần. Trên dữ liệu gần sắp (xáo trộn 1%), nó vẫn ~O(n) và vẫn nhanh hơn quicksort 15 lần. Insertion sort là thuật toán nhanh nhất thế giới cho dữ liệu đã hoặc gần có thứ tự.
Một lần tôi đo hớ: "O(n²)" là ca xấu, không phải mọi ca
Cú hớ của tôi là cú hớ mà cả ngành hay mắc: nhìn thấy "O(n²)" và kết luận ngay "chậm, bỏ đi". Tôi vào bài định viết insertion sort như một thuật toán giáo khoa, một bậc thang để leo lên các thuật toán O(n log n) thật sự dùng được. Đo xong tôi phải viết lại: insertion sort thắng ở hai vùng lớn của thực tế — mảng nhỏ và dữ liệu gần sắp — và cả hai vùng đó rất thường gặp.
Sai lầm nằm ở việc đọc một ký hiệu tiệm cận như một phán quyết tuyệt đối. Big-O mô tả hành vi khi n → ∞ trên ca xấu nhất; nó cố ý vứt bỏ hằng số và bỏ qua n nhỏ. Nhưng chương trình thật sắp xếp rất nhiều mảng nhỏ (nghĩ tới việc sắp từng nhóm nhỏ bên trong một thuật toán lớn hơn), và rất nhiều dữ liệu gần sắp (danh sách vừa thêm vài phần tử, log gần như theo thời gian). Ở đúng những chỗ đó, nhãn "O(n²)" là một lời nói dối về hiệu năng thực, vì nó mô tả một ca mà bạn không rơi vào. Bài học đo lường: một nhãn độ phức tạp là điều xấu nhất tiệm cận, không phải điều bạn sẽ đo trên dữ liệu thật — và với n nhỏ hay dữ liệu có cấu trúc, "thuật toán tệ" có thể là lựa chọn tốt nhất. Đây chính là lý do các thư viện sắp xếp nhanh (như introsort và timsort, chủ đề bài tới) không chạy quicksort thuần: chúng chuyển sang insertion sort cho mọi mảng con nhỏ, và timsort còn dò các đoạn đã sắp sẵn để tận dụng tính adaptive. "Thuật toán để dạy" hóa ra nằm trong ruột của mọi thuật toán để dùng.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng đọc big-O như một thứ hạng cố định; hỏi n của bạn lớn cỡ nào và dữ liệu có cấu trúc gì. Nếu bạn sắp những mảng vài chục phần tử — điều xảy ra liên tục bên trong các thuật toán khác — một insertion sort gọn có thể nhanh hơn một lời gọi thư viện tổng quát, vì nó không trả phí thiết lập. Và nếu dữ liệu của bạn gần như đã có thứ tự, insertion sort (hoặc một sort adaptive như timsort dựa trên nó) sẽ về gần O(n), trong khi một quicksort ngây thơ vẫn trả đủ O(n log n).
Hệ quả thứ hai: biết vì sao thư viện chuẩn làm những gì chúng làm. Khi bạn thấy nguồn của một hàm sort "nhanh" có một nhánh if (n < 16) insertion_sort(...), đó không phải chắp vá — đó là kết quả của đúng phép đo crossover bạn vừa thấy. Hiểu điều này giúp bạn không "tối ưu" nhầm bằng cách bỏ nhánh đó đi, và giúp bạn tự viết được ngưỡng đúng nếu cần cài sort riêng.
Hệ quả thứ ba là con số mang theo: insertion sort O(n²) nhưng thắng quicksort ở mảng nhỏ (tới ~128 phần tử) nhờ hằng số bé, và adaptive nên trên mảng đã sắp nó chỉ O(n) — 0,09ms so với quicksort 1,7ms, nhanh hơn 19 lần; nó chỉ chậm (2477ms) trên dữ liệu lớn và hỗn độn. Nhãn độ phức tạp cho bạn biết ca xấu nhất khi n ra vô cùng; nó không cho bạn biết chương trình của bạn — với n thật và dữ liệu thật — sẽ chạy nhanh hay chậm. Chỉ đồng hồ mới cho biết điều đó.
Thử ba mươi giây
Lần tới khi bạn định gạt bỏ một thuật toán chỉ vì thấy "O(n²)", hỏi hai câu: n của tôi có nhỏ không, và dữ liệu của tôi có gần sắp không? Nếu bạn đang sắp những nhóm chục phần tử, hoặc một danh sách gần như đã đúng thứ tự chỉ lệch vài chỗ, hãy thử đo insertion sort so với lời gọi sort mặc định — rất có thể nó nhanh hơn, và đơn giản hơn. Cách thử nhanh nhất cho tính adaptive: lấy một mảng đã sắp, đảo vài phần tử, rồi sắp lại bằng insertion sort và bằng một sort O(n log n), và bấm giờ cả hai. Bạn sẽ thấy insertion sort về gần như tức thì, còn cái kia vẫn làm đủ phần việc O(n log n) của nó. Đó là lúc "O(n²)" trên giấy và con số trên đồng hồ nói hai điều hoàn toàn khác nhau — và đồng hồ là cái đúng.
