Sắp xếp chèn là một thuật toán đơn giản để sắp xếp mảng (hoặc danh sách) theo từng phần tử thông qua các phép so sánh. Thuật toán này không hiệu quả bằng các thuật toán nâng cao hơn như quicksort, heapsort, hoặc merge sort khi áp dụng cho các danh sách lớn. Tuy nhiên, sắp xếp chèn có một số ưu điểm:
- Dễ hiểu và triển khai: Jon Bentley đã chỉ ra một phiên bản C/C++ chỉ 3 dòng code, được tối ưu hóa chỉ còn 5 dòng.[1]
- Hiệu quả đối với những tập dữ liệu nhỏ, tương tự như các thuật toán sắp xếp bậc hai (O(n^2))
- Hiệu quả hơn trong thực tế so với hầu hết các thuật toán bậc hai đơn giản khác như selection sort hoặc bubble sort
- Phù hợp với dữ liệu gần như đã được sắp xếp: độ phức tạp thời gian là O(kn) khi mỗi phần tử trong danh sách cách vị trí sắp xếp của nó không quá k vị trí
- Bảo toàn thứ tự tương đối của các phần tử có cùng khóa
- Tính nội tại: chỉ đòi hỏi một lượng bộ nhớ bổ sung hằng số O(1)
- Trực tuyến: có thể sắp xếp một danh sách ngay khi nhận được nó
Khi mọi người sắp xếp thủ công các quân bài trong một tay bài, hầu hết mọi người sử dụng một phương pháp tương tự sắp xếp chèn.[2]