113 DCHECK_LE(values.size(),
114 static_cast<size_t>(std::numeric_limits<uint32_t>::max()));
115 const uint32_t size = values.size();
124 std::vector<uint32_t> count(num_passes << radix_width, 0);
125 uint32_t*
const count_ptr = count.data();
129 constexpr uint32_t kRadixMask = (1 << radix_width) - 1;
130 for (
const T value : values) {
131 for (
int p = 0; p < num_passes; ++p) {
132 ++count_ptr[(p << radix_width) +
133 ((absl::bit_cast<U>(value) >> (radix_width * p)) &
139 uint32_t sum[num_passes] = {};
140 for (
int i = 0; i < (1 << radix_width); ++i) {
142 for (
int p = 0; p < num_passes; ++p) {
143 const uint32_t old_sum = sum[p];
144 sum[p] += count_ptr[(p << radix_width) + i];
145 count_ptr[(p << radix_width) + i] = old_sum;
161 constexpr int kNumBitsInTopRadix =
162 std::numeric_limits<U>::digits - (num_passes - 1) * radix_width;
164 if constexpr (std::is_integral_v<T> && std::is_signed_v<T> &&
165 kNumBitsInTopRadix > 0 && kNumBitsInTopRadix <= radix_width) {
166 uint32_t*
const last_pass_count =
167 count_ptr + ((num_passes - 1) << radix_width);
168 const uint32_t num_nonnegative_values =
169 last_pass_count[1 << (kNumBitsInTopRadix - 1)];
170 if (num_nonnegative_values != size) {
176 const uint32_t num_negative_values = size - num_nonnegative_values;
177 for (
int i = 0; i < (1 << (kNumBitsInTopRadix - 1)); ++i) {
179 last_pass_count[i] += num_negative_values;
181 last_pass_count[i + (1 << (kNumBitsInTopRadix - 1))] -=
182 num_nonnegative_values;
188 std::vector<T> tmp(size);
189 T* from = values.data();
192 for (
int pass = 0; pass < num_passes; ++pass, radix += radix_width) {
193 uint32_t*
const cur_count_ptr = count_ptr + (pass << radix_width);
194 const T*
const from_end = from + size;
195 for (T* ptr = from; ptr < from_end; ++ptr) {
196 to[cur_count_ptr[(absl::bit_cast<U>(*ptr) >> radix) & kRadixMask]++] =
204 if constexpr (!std::is_integral_v<T> && std::is_signed_v<T> &&
205 kNumBitsInTopRadix > 0 && kNumBitsInTopRadix <= radix_width) {
206 uint32_t*
const last_pass_count =
207 count_ptr + ((num_passes - 1) << radix_width);
208 const uint32_t num_nonnegative_values =
209 last_pass_count[(1 << (kNumBitsInTopRadix - 1)) - 1];
210 if (num_nonnegative_values != size) {
214 const uint32_t num_negative_values = size - num_nonnegative_values;
215 if constexpr (num_passes % 2) {
218 std::memcpy(values.data() + num_negative_values, tmp.data(),
219 num_nonnegative_values *
sizeof(T));
221 DCHECK_EQ(from, tmp.data());
222 for (uint32_t i = 0; i < num_negative_values; ++i) {
223 values[i] = from[size - 1 - i];
228 std::memcpy(tmp.data(), values.data() + num_nonnegative_values,
229 num_negative_values *
sizeof(T));
233 std::memmove(values.data() + num_negative_values, values.data(),
234 num_nonnegative_values *
sizeof(T));
235 DCHECK_EQ(
to, tmp.data());
236 for (uint32_t i = 0; i < num_negative_values; ++i) {
237 values[i] =
to[num_negative_values - 1 - i];
247 if constexpr (num_passes % 2) {
248 std::memcpy(values.data(), from, size *
sizeof(T));
273 if constexpr (!std::is_integral_v<T>) {
274 DCHECK_EQ(num_bits,
sizeof(T) * 8);
275 }
else if (!values.empty()) {
276 auto minmax_it = absl::c_minmax_element(values);
277 const T min_val = *minmax_it.first;
278 const T max_val = *minmax_it.second;
280 DCHECK_EQ(max_val, 0);
282 using U = std::make_unsigned_t<T>;
285 DCHECK_LE(
static_cast<U
>(max_val) >> (num_bits - 1), 1);
286 DCHECK_LE(
static_cast<U
>(min_val) >> (num_bits - 1), 1);
294 if (values.size() < 300) {
295 absl::c_sort(values);
301 if (num_bits <= 16) {
307 }
else if (num_bits <= 32) {
308 if (values.size() < 1000) {
309 if (num_bits <= 24) {
314 }
else if (values.size() < 2'500'000) {
315 if (num_bits <= 22) {
323 }
else if (num_bits <= 64) {
324 if (values.size() < 5000) {
325 absl::c_sort(values);
326 }
else if (values.size() < 1'500'000) {
327 if (num_bits <= 33) {
329 }
else if (num_bits <= 44) {
331 }
else if (num_bits <= 55) {
337 if (num_bits <= 48) {
344 LOG(DFATAL) <<
"RadixSort() called with unsupported value type";
345 absl::c_sort(values);