Động lực

Counting Sort không bao giờ so sánh hai phần tử. Thuật toán dùng trực tiếp giá trị của chúng làm chỉ số trong mảng count, nhờ đó chạy trong thời gian tuyến tính.

Tại sao nên học Counting Sort?

• Thời gian tuyến tính: thuật toán chạy trong O(n + k), trong đó n là số phần tử và k là phạm vi giá trị. Khi k nhỏ, cách này nhanh hơn O(n log n).
• Ổn định (khi thực hiện cẩn thận): đây là nền tảng của Radix Sort, thuật toán kết hợp nhiều lượt sắp xếp bằng đếm.
• Một ý tưởng khác: sắp xếp bằng cách đếm số lần xuất hiện của các giá trị thay vì so sánh chúng.

Đánh đổi là thuật toán cần O(k) bộ nhớ cho mảng đếm, nên không phù hợp khi phạm vi giá trị quá lớn (ví dụ: sắp xếp một vài số có giá trị lên đến một tỷ).