Động lực

Radix Sort không bao giờ so sánh trực tiếp hai số. Thuật toán nhóm các số theo từng chữ số một bằng một thuật toán sắp xếp phụ ổn định, nhờ đó vượt qua giới hạn O(n log n) mà các thuật toán sắp xếp dựa trên so sánh không thể vượt qua.

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

• Thời gian gần tuyến tính: thuật toán chạy trong O(d * (n + k)), với d là số chữ số và k là cơ số (ở đây là 10). Với các số có số chữ số bị giới hạn, độ phức tạp thực tế là O(n).
• Ổn định: các giá trị bằng nhau giữ nguyên thứ tự tương đối, nhờ vậy các lượt xử lý từng chữ số kết hợp chính xác với nhau.
• Một ý tưởng khác biệt: thuật toán cho thấy sắp xếp không nhất thiết phải dựa trên so sánh, một nhận định quan trọng khi xử lý số nguyên lớn hoặc khóa có độ rộng cố định.

Điểm đánh đổi: thuật toán cần các khóa có thể tách thành chữ số (ở đây là số nguyên không âm) và cần thêm một ít bộ nhớ cho các nhóm.