Tổng quan
Insertion Sort mở rộng vùng đã sắp ở đầu mảng. Nó lấy phần tử kế tiếp và chèn vào đúng chỗ giữa các phần tử đã sắp, dịch các phần tử lớn hơn sang bên — giống như sắp một tay bài.
Insertion Sort hoạt động thế nào?
- Bắt đầu với phần tử đầu tiên được coi là đã sắp.
- Lấy phần tử kế tiếp ('key') từ phần chưa sắp.
- Dịch mọi phần tử đã sắp lớn hơn sang phải một ô để tạo khoảng trống.
- Đặt key vào khoảng trống, rồi lặp lại cho các phần tử còn lại.
Khi nào nên dùng?
- Mảng nhỏ và dữ liệu gần như đã sắp, khi nó tiệm cận O(n).
- Sắp xếp trực tuyến — có thể sắp một luồng ngay khi phần tử đến.
- Làm trường hợp cơ sở trong các sort lai (ví dụ ngưỡng mảng con nhỏ trong Quick Sort / Timsort).
Phân tích độ phức tạp
Ở trường hợp xấu nhất (sắp ngược) mỗi key phải dịch qua mọi phần tử trước đó, cho O(n²). Với đầu vào gần như đã sắp thì ít phải dịch, nên tiệm cận O(n) — điểm mạnh trường hợp tốt nhất. Nó tại chỗ và ổn định.
Câu hỏi thường gặp
Khi nào Insertion Sort thực sự là lựa chọn tốt?
Với mảng nhỏ hoặc gần như đã sắp, nó thường nhanh hơn các sort O(n log n) nhờ chi phí thấp và trường hợp tốt nhất O(n). Vì thế các thư viện chuyển về nó cho các mảng con rất nhỏ.
Insertion Sort có ổn định không?
Có — nó chỉ dịch các phần tử lớn hơn key thực sự, nên các phần tử bằng nhau giữ nguyên thứ tự tương đối.