Ok, so first of all i don't know if it exist. But i will share my algorithm here only.

MOTIVATION!

Radix sort with base > 10?

so my motivation came when i though of why can't we use base 1e5 or 1e6 in radix sort? and i came up with following idea.

Most of the questions on CF have limit of values <=1e9. So my algorithm focuses majorily on that thing.

Alogirthm.

let us define a constant base, now we will make groups on the basis of ai % base,

• group[j] -> contains ai / base of those whoose ai % base == j.
• counts[j] -> it will store total number of times ai / base is equal to j. Note that both arrays will be of length base.

Next question — Now, how can we find the index(in sorted array) of any value of any group?

Observe, let x be any value of group[i], then value = x * base + i, its index will be atleast bigger than prefix Sum of counts[i] upto x — 1, also value will be bigger than those value whoose group number is smaller with same x.

Final touch

1. After making groups, and counts make prefix array of counts(let us call that array pref).
2. Define another array Live of length base, (initate all elements with 0).
3. Iterate from group 0 -> base. Now for every element(x) in this group(i) do the following
   • value = x * base + i
   • the index of this value = pref[x — 1] + live[x]
   • now do live[x] += 1
   • Update array[index] = value.
4. the sorting is done!

Implementation!

void sortit(vector<int> &arr, int base = 1 << 15) {
    int n = arr.size();
    
    vector<vector<int>> grps(base);
    vector<int> cnts(base + 1), live(base);
    for (int i = 0; i < n; i++) {
        int z = arr[i] / base;
        grps[arr[i] % base].push_back(z);//adding each element in respective group
        cnts[z + 1]++;//increasing count
    }
    for (int i = 1; i < base; i++) cnts[i] += cnts[i - 1]; //making prefix array
    
    for (int i = 0; i < base; i++) {
        for (int &x : grps[i]) arr[cnts[x] + live[x]++] = x * base + i;
    }
}

Analysis.

For all values less than base^2(base = 2^15), the time complexity comes out to be O(n + base), 2 * n(2 for loops of n) + base(memory definition and prefix array). you can choose base depending on max value of array, N and memory.

For n > base it starts becoming faster and faster than cpp sort.

Results.

These results are when i ran them on my laptop. UPD- Added radix sort comparison also!

Size 1000 Sorting....

Time taken by sortit() -> 1ms
Time taken  by cpp sort() -> 0ms
Time taken by radix sort(base 256)(4 rounds) -> 0ms
Time taken by radix sort(base 1 << 16)(2 rounds) -> 4ms

Size 10000 Sorting....

Time taken by sortit() -> 1ms
Time taken  by cpp sort() -> 1ms
Time taken by radix sort(base 256)(4 rounds) -> 1ms
Time taken by radix sort(base 1 << 16)(2 rounds) -> 5ms

Size 100000 Sorting....

Time taken by sortit() -> 9ms
Time taken  by cpp sort() -> 15ms
Time taken by radix sort(base 256)(4 rounds) -> 5ms
Time taken by radix sort(base 1 << 16)(2 rounds) -> 18ms

Size 1000000 Sorting....

Time taken by sortit() -> 40ms
Time taken  by cpp sort() -> 185ms
Time taken by radix sort(base 256)(4 rounds) -> 54ms
Time taken by radix sort(base 1 << 16)(2 rounds) -> 90ms

Size 10000000 Sorting....

Time taken by sortit() -> 316ms
Time taken  by cpp sort() -> 2171ms
Time taken by radix sort(base 256)(4 rounds) -> 572ms
Time taken by radix sort(base 1 << 16)(2 rounds) -> 508ms

Size 100000000 Sorting....

Time taken by sortit() -> 3056ms
Time taken  by cpp sort() -> 24149ms
Time taken by radix sort(base 256)(4 rounds) -> 5747ms
Time taken by radix sort(base 1 << 16)(2 rounds) -> 4749ms

Size 1000000000 Sorting....

Time taken by sortit() -> 35071ms
Time taken  by cpp sort() -> 277987ms
Time taken by radix sort(base 256)(4 rounds) -> 65696ms
Time taken by radix sort(base 1 << 16)(2 rounds) -> 50732ms

For higher values of n, it tends to become faster. Hence, this is suitable for higher n values.

If you find any similar or same algorithm, please let me know!