template <typename T>
static inline unsigned
bit(T i, unsigned b) {
// Return the b-th bit of the given integral value; the leftmost bit is 0.
const unsigned shift = sizeof(T)*8 - (b + 1);
return (i & (1 << shift)) >> shift;
}
template <typename T>
static T *
partition(T * left, T * right, unsigned b) {
while (left < right)
if (0 == bit(*left, b)) left++;
else if (1 == bit(*(right - 1), b)) right--;
else {
const T tmp = *left;
*left++ = *--right;
*right = tmp;
}
assert(left == right);
return left;
}
template <typename T>
void
re_sort(T * left, T * right, unsigned bit = 0) {
if ((left + 1 < right) and (bit < sizeof(T)*8)) {
T * const mid = partition(left, right, bit);
re_sort(left, mid, bit + 1);
re_sort(mid, right, bit + 1);
}
}
This page last modified on 24 January 2006.