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 of any value of any group?
Observe, let x be any value of group[i], then value = x * base + i, 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.
Final touch
- After making groups, and counts make prefix array of counts(let us call that array pref).
- Define another array Live of length base, (initate all elements with 0).
- 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.
You have index of every value in the sorted array now, hence the sorting is done!
