Ah, I know my book had an example of a bucket sort, actually.

The idea is this:

Make several buckets. Each bucket can hold one type of item only. So every item you find of a type you place into that bucket.

Then you keep your buckets sorted so you know which bucket contains the biggest item and which the lowest.

After sorting all your data into your buckets, you do the reverse: you begin with the biggest (or lowest) bucket, you empty its contents into your new data set and gradually go from the biggest to lowest (or the other way around).

Well, that sounds awfully abstract. What does it mean? Let's take an example with integers.

In this case, we can let each bucket represent a number. So each bucket contains a number of the same number. Let's say we simplify this by putting the number of said items in the same bucket.

For example, say we have, in our data to sort, 1 3 5 5 7 2.

Create buckets 1, 3, 5, 7 and 2. Put into bucket 1, 1, into bucket 3, 1, into bucket 5, 2, into bucket 7, 1 and into bucket 2, 1 (the occurrences of each number in our data to sort).

Now, let's do this in reverse. Begin with the biggest bucket, empty it into the sorted data, then continue with the next, and so on.

So it might look like:

Take lowest bucket 1, empty into data stream:

1

Bucket 2:

1 2

Bucket 3:

1 2 3

Bucket 5:

1 2 3 5 5

Bucket 7:

1 2 3 5 5 7

And we're done.

An example of an implementation may be this:

Code:

#include <vector>
#include <limits>
template<typename InputIt, typename OutputIt>
void Sort(InputIt InputBegin, InputIt InputEnd, OutputIt OutputStart)
{
typedef typename InputIt::value_type It_t;
std::vector<It_t> buckets(std::numerical_limits<InputIt>::max());
while (InputBegin++ != InputEnd)
buckets(*InputBegin)++;
for (auto it = buckets.begin(), end = buckets.end(); it != end; ++it)
{
for (It_t i = 0; i < *it; i++)
*OutputStart++ = *it;
}
}