Cách hoạt động?

Counting Sort hoạt động qua hai giai đoạn: đếm, sau đó tạo lại.

Quy trình từng bước:

1. Đếm: tạo một mảng count, trong đó count[v] cho biết giá trị v xuất hiện bao nhiêu lần.
2. Tạo lại: duyệt các giá trị từ nhỏ nhất đến lớn nhất và ghi mỗi giá trị v vào đầu ra count[v] lần.

Ví dụ với [4, 2, 2, 8, 3, 3, 1]:

• Đếm từng giá trị: 1 xuất hiện một lần, 2 hai lần, 3 hai lần, 4 một lần, 8 một lần.
• Tạo lại theo thứ tự: [1, 2, 2, 3, 3, 4, 8].

Không có phép so sánh nào được thực hiện: chính giá trị quyết định vị trí của mỗi phần tử.