radix256.cpp

#include <iostream>
#include <vector>
#include <deque>
#include <iterator>
#include <algorithm>
using namespace std;

// We can speed it up by switching to base 256. 256 = 0xff or one byte. We divide by
// 256 by shifting 8 bits to the right. 

void radix_sort_base256(vector<unsigned int> & x)
{
    if ( x.empty() ) {

    	return; // need at least one element
    }

    typedef vector<unsigned int> input_type;

    // buckets_type is a deque of deques of unsigned ints.
    typedef deque< deque < input_type::value_type > > buckets_type;

    
    buckets_type buckets(256); // allocate buckets for sorting by base 256 numbers
                               // each element is a deque of unsigned int.

    // find maximum in the array to limit the main loop below
    input_type::value_type max = *max_element(x.begin(), x.end()); 

    // We sort while we still have base256 "columns" to examine. 
  
    // Note: Instead of using the division operator below, for example
    //
    //    for(; max != 0 ; max /= 256, pow256 *= 256) {
    //
    // we instead simply shift right to multiply by powers of 256.
    for(auto bits_2shift = 0; max != 0 ; max >>= 8, bits_2shift += 8)   {

        // 1. determine which bucket each element in x should enter
        for(input_type::const_iterator elem = x.begin(); elem != x.end(); ++elem) {

                // Use current rightmost digit to determine bucket number
                // We shift right to multiply by successive powers of 256, then do
                // bitwise AND to get the last base256 digit.  This process is faster
                // than doing:
                //
                // int const bucket_num = ( *elem / pow256 ) % 256;
                int const bucket_num = ( *elem >> bits_2shift) & 0xff; 

                // add the element to the list in the bucket:
                buckets[ bucket_num ].push_back( *elem );
        }

        // 2. transfer results of buckets back into the main input array.
        input_type::iterator store_pos = x.begin();

        // for each bucket:
        for(buckets_type::iterator bucket = buckets.begin(); bucket != buckets.end(); ++bucket) {

                // for each element in the bucket:
                for(buckets_type::value_type::const_iterator bucket_elem = bucket->begin();
                        bucket_elem != bucket->end(); ++bucket_elem)  {

                        // copy the element into next position in the main array
                        *store_pos++ = *bucket_elem;
                }

                bucket->clear(); // forget the current bucket's list of numbers
        }
    }
}