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. 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!
