ハトの巣ソート（ピジョンソート、Pigeon sort）。
いまいち理解できていないので、Wikipedia様に丸投げ→→「Pigeonhole sort」。（ 18:06, 19 March 2008版には擬似コードもあり。）
メモリは食うけど、ソートは馬鹿早い。同じ要素の並びは変わらない安定ソート。
追記＠2008-05-12T23:39+09:00：新しいバージョンをアップ。
/* データはユニークである必要があります。 */
template<typename TElement, typename TSize>
void PigeonholeSort(TElement * data, const TSize size)
{
TElement min = data[0];
TElement max = min;
for (TSize i = 1; i < size; ++i) {
min = data[i] < min ? data[i] : min;
max = data[i] > max ? data[i] : max;
}
TSize range = max - min + 1;
TElement * pigeonholes = new TElement[range];
for (TSize i = 0; i < range; ++i)
pigeonholes[i] = 0; /* memsetで十分。 */
for (TSize i = 0; i < size; ++i)
pigeonholes[data[i]-min] = data[i];
TSize dataPos = 0;
for (TSize i = 0; i < range; ++i)
if (pigeonholes[i] != 0)
data[dataPos++] = i + min;
delete[] pigeonholes;
}
追記@2008-05-08T17:19+09:00：下記のコードはちょっと間違えています。そのうち修正しますので、くれぐれも参考にしないよう、お願いします。
#include <map>
template<typename TElement, typename TSize>
void PigeonholeSort(TElement * data, const TSize size)
{
typedef std::map<TElement, std::vector<TElement> > TMap;
TMap pigeonholes;
for (TSize i = 0; i < size; ++i)
pigeonholes[data[i]].push_back(data[i]);
TSize dataPos = 0;
const TMap::const_iterator end = pigeonholes.end();
for (TMap::iterator it = pigeonholes.begin(); it != end; ++it)
{
const TMap::value_type & pigeonhole = *it;
const TSize size = pigeonhole.second.size();
for (TSize i = 0; i < size; ++i)
{
data[dataPos++] = pigeonhole.first;
}
}
}