## Discussion¶

This is an implementation of the radix sort algorithm that uses base 256.

## Source Code¶

This uses base 256 to do the radix sort

```#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.

{
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
}
}
}
```

Main test program

```#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

int RandomNumber ()
{
return (rand() % 1000);
}

int main(int argc, char** argv)
{
vector<unsigned> input(20);

generate (input.begin(), input.end(), RandomNumber);

// using built-in random generator:
random_shuffle ( input.begin(), input.end() );

cout << " ** Elements before sorting: " << endl;

copy(input.begin(), input.end(), ostream_iterator<unsigned int>(cout, " "));