Credits for the original implementation I based my code on:
Quora - What is the most efficient way to sort a million 32-bit integers?
Implementation
// RadixSort - works for values up to unsigned_int_max (32-bit)
template<typename Iter>
void radix_sort(Iter __first, Iter __last){
typedef typename iterator_traits<Iter>::value_type value_type;
vector<value_type> out(__last - __first);
// calculate most-significant-digit (256-base)
value_type __mx = *max_element(__first, __last); //O(n)
int __msb = 0;
do {
__msb += 8;
__mx = __mx >> 8;
} while(__mx);
Iter __i, __j, __s;
bool __swapped = false;
for (int __shift = 0; __shift < __msb; __shift += 8) {
// cycle input/auxiliar vectors
if (__swapped) {
__i = out.begin();
__j = out.end();
__s = __first;
}
else {
__i = __first;
__j = __last;
__s = out.begin();
}
// counting_sort
size_t count[0x100] = {};
for (Iter __p = __i; __p != __j; __p++)
count[(*__p >> __shift) & 0xFF]++;
// prefix-sum
size_t __m, __q = 0;
for (int i = 0; i < 0x100; i++) {
__m = count[i];
count[i] = __q;
__q += __m;
}
// filling result
Iter __v;
for (Iter __p = __i; __p != __j; __p++) {
__v = __s + count[(*__p >> __shift) & 0xFF]++;
*__v = *__p;
}
__swapped = !__swapped;
}
// if ended on auxiliar vector, copy to input vector
if (__swapped) copy(out.begin(), out.end(), __first); //O(n)
}
Discussion
In order to implement a more general algorithm than the one used as reference, I tried to refactor the code using template
and iterators
. This is the main difference between my code and the original.
I can't simply swap references when using iterators, so I approached this problem by cycling the iterators used in each counting-sort loop. Doing so prevents the need to copy the output array on every loop.
Another different aspect of my code is that I find max-element and calculate the most-significant-digit on base-256. I use this information to determine how many counting-sort loops are necessary, instead of hardcoding 32 (unsigned_max) and always running the loop 4-times even if all values are less than 255. This actually adds unnecessary overhead if 4-loops are necessary, but it should increase execution time otherwise.
The temporary container used is a vector<value_type>
and this is something I'm not quite sure about, I feel like this is a point where I could improve my code. I'd like to hear opinions about it.
Questions
- What are possible improvements that can be made to my implementation?
- How would you re-factor the iterator cycle I used? (I hate it)
- Which container should I use for the temp-array?
- Should I use
std::copy
orstd::move
to move the data from the temp-array to the input container?
Relevant Information
I decided to run some benchmarks to test if calculating the maximum-digit makes a huge difference. element_values
defines the range of values each element can have. The maximum-digit only affects the number of loops if element_values
can be represented with 24-bits or less. Here are the results for n = 1E7
:
element_values < 256 (8-bits):
radix_sort_msd - Average time: 51.59 ms
radix_sort_32 - Average time: 109.03 ms
element_values < UINT_MAX(32-bits):
radix_sort_msd - Average time: 107.38 ms
radix_sort_32 - Average time: 89.75 ms
While radix_sort_msd
works really well when element_values
is small, it really just depends on the dataset. Therefore implementing is a matter of preference.