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

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

• O(d * (n + k))
  • trong đó n là số phần tử, k là cơ số (10) và d là số chữ số trong giá trị lớn nhất. Mỗi lượt trong d lượt thực hiện O(n + k) thao tác.
• Khi d nhỏ và cố định, độ phức tạp này tương đương O(n), nhanh hơn O(n log n) của các thuật toán sắp xếp bằng phép so sánh.

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

• O(n + k)
  • Mỗi lượt tạo một mảng đầu ra có kích thước n và một mảng đếm có kích thước k.

Tóm tắt:

• Radix Sort là thuật toán sắp xếp ổn định, không dùng phép so sánh, có thể nhanh hơn O(n log n) khi sắp xếp các khóa số nguyên có số chữ số bị giới hạn.
• Thuật toán cần các khóa có thể tách thành chữ số và cần thêm một ít bộ nhớ; phiên bản này giả định các số nguyên không âm.