Độ phức tạp về thời gian và không gian

Độ phức tạp thời gian:

• O(n + k)
  • trong đó n là số phần tử và k là phạm vi giá trị (giá trị lớn nhất + 1). Duyệt một lần để đếm, rồi duyệt một lần qua các số đếm để tạo lại mảng.
• Khi k nhỏ và cố định, độ phức tạp thực tế là O(n), nhanh hơn O(n log n) của các thuật toán sắp xếp so sánh.

Độ phức tạp không gian:

• O(n + k)
  • Mảng đếm dùng O(k) và đầu ra dùng O(n).

Tóm tắt:

• Counting Sort là thuật toán sắp xếp ổn định, không dựa trên so sánh và chạy trong thời gian tuyến tính khi phạm vi số nguyên nhỏ.
• Thuật toán này không phù hợp khi phạm vi giá trị k rất lớn, vì mảng đếm sẽ rất lớn. Phiên bản này giả định các số nguyên không âm.