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
- 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.
- 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.
Size 1000 Sorting....
Time taken by sortit() -> 1ms
Time taken by cpp sort() -> 0ms
Size 10000 Sorting....
Time taken by sortit() -> 2ms
Time taken by cpp sort() -> 1ms
Size 100000 Sorting....
Time taken by sortit() -> 9ms
Time taken by cpp sort() -> 15ms
Size 1000000 Sorting....
Time taken by sortit() -> 43ms
Time taken by cpp sort() -> 186ms
Size 10000000 Sorting....
Time taken by sortit() -> 331ms
Time taken by cpp sort() -> 2117ms
Size 100000000 Sorting....
Time taken by sortit() -> 3024ms
Time taken by cpp sort() -> 24147ms
Size 1000000000 Sorting....
Time taken by sortit() -> 50924ms
Time taken by cpp sort() -> 277987ms
For higher values of n, it tends to become faster.
If you find any similar or same algorithm, please let me know!
