radix_sort.h

#ifndef RADIX_SORT_H
#define RADIX_SORT_H
 
#ifdef __cplusplus
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <vector>
#endif
 
namespace {
template <typename T> void countingSortForRadix(std::vector<T>& arr, int exp) {
    int64_t n = arr.size();
    std::vector<T> output(n);
    std::vector<int> count(10, 0);
 
    for (int64_t i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }
 
    for (int64_t i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
 
    for (int64_t i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
 
    arr = output;
}
} // namespace

template <typename T> void radix_sort(std::vector<T>& arr) {
    T maxElement = *max_element(arr.begin(), arr.end());
 
    for (int exp = 1; maxElement / exp > 0; exp *= 10) {
        countingSortForRadix(arr, exp);
    }
}
 
#endif // RADIX_SORT_H