38 #ifndef STK_UTIL_UTIL_RADIXSORT_HPP 39 #define STK_UTIL_UTIL_RADIXSORT_HPP 48 inline void swap_impl( T& a, T& b )
57 inline void insertion_sort_impl( T* a,
size_t a_size )
59 for (
size_t i = 1; i < a_size; ++i )
61 if ( a[ i ] < a[ i - 1 ] )
63 T currentElement = a[ i ];
66 for ( j = i - 1; j > 0 && currentElement < a[ j - 1 ]; --j )
70 a[ j ] = currentElement;
85 template<
class T,
unsigned long PowerOfTwoRadix,
unsigned long Log2ofPowerOfTwoRadix,
long Threshold >
86 inline void radix_sort_unsigned_impl( T* a,
long last, T bitMask,
unsigned long shiftRightAmount )
88 unsigned long count[ PowerOfTwoRadix ];
89 for(
unsigned long i = 0; i < PowerOfTwoRadix; ++i ) count[ i ] = 0;
90 for (
long _current = 0; _current <= last; ++_current ) count[ (unsigned long)(( a[ _current ] & bitMask ) >> shiftRightAmount ) ]++;
92 long startOfBin[ PowerOfTwoRadix + 1 ], endOfBin[ PowerOfTwoRadix ], nextBin = 1;
93 startOfBin[ 0 ] = endOfBin[ 0 ] = 0; startOfBin[ PowerOfTwoRadix ] = -1;
94 for(
unsigned long i = 1; i < PowerOfTwoRadix; ++i )
95 startOfBin[ i ] = endOfBin[ i ] = startOfBin[ i - 1 ] + count[ i - 1 ];
97 for (
long _current = 0; _current <= last; )
100 T _current_element = a[ _current ];
101 while( endOfBin[ digit = (
unsigned long)(( _current_element & bitMask ) >> shiftRightAmount )] != _current ) swap_impl( _current_element, a[ endOfBin[ digit ]++ ] );
102 a[ _current ] = _current_element;
105 while( endOfBin[ nextBin - 1 ] == startOfBin[ nextBin ] ) ++nextBin;
106 _current = endOfBin[ nextBin - 1 ];
108 bitMask >>= Log2ofPowerOfTwoRadix;
111 if ( shiftRightAmount >= Log2ofPowerOfTwoRadix ) shiftRightAmount -= Log2ofPowerOfTwoRadix;
112 else shiftRightAmount = 0;
114 for(
unsigned long i = 0; i < PowerOfTwoRadix; ++i )
116 long numberOfElements = endOfBin[ i ] - startOfBin[ i ];
117 if ( numberOfElements >= Threshold )
118 radix_sort_unsigned_impl< T, PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( &a[ startOfBin[ i ]], numberOfElements - 1, bitMask, shiftRightAmount );
119 else if ( numberOfElements >= 2 )
120 insertion_sort_impl( &a[ startOfBin[ i ]], numberOfElements );
154 void radix_sort_unsigned( T* a,
size_t a_size )
156 const long Threshold = 25;
157 const unsigned long PowerOfTwoRadix = 256;
158 const unsigned long Log2ofPowerOfTwoRadix = 8;
160 if ( a_size >= (
size_t)Threshold ) {
161 if (a_size > (
size_t)std::numeric_limits<long>::max()) {
162 std::ostringstream msg ;
163 msg <<
"stk_classic::utility::radix_sort() exceeded allowable array size (";
164 msg << a_size <<
" < " << std::numeric_limits<long>::max() <<
")";
165 throw std::runtime_error( msg.str() );
167 unsigned long shiftRightAmount =
sizeof(T) * 8 - Log2ofPowerOfTwoRadix;
168 T bitMask = (T)( ((T)( PowerOfTwoRadix - 1 )) << shiftRightAmount );
169 radix_sort_unsigned_impl< T, PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( a, a_size - 1, bitMask, shiftRightAmount );
172 insertion_sort_impl( a, a_size );
eastl::iterator_traits< InputIterator >::difference_type count(InputIterator first, InputIterator last, const T &value)