符号なし整数型配列内の要素数を重複を除いてカウントする - Counting Sortの応用

『OKWave - アルゴリズムの名前を教えてください』: http://okwave.jp/qa2722011.html

unsigned short data[1000];
/* data[]には適当なデータが入るとする */

int i;
int count = 0;
unsigned short flag[0x10000];
unsigned short link[0x10000];
int n;

for(i = 0; i < 1000; i++) {
　n = data[i];
　if(flag[n] >= count || link[flag[n]] != n) {
　　flag[n] = count;
　　link[count] = n;
　　count++;
　}
}

１年位前にメモして以来、理解できなくてほったらかしにしていたのを、ふと思い出したので、ちょっと時間かけて読み解いてみた。理解するに当たっては、Counting Sort(分布数え上げソート)の考え方が参考になった。

『ソースコード探険隊 > アルゴリズムとデータ構造 > アルゴリズム > 分布数え上げソート』: http://www.codereading.com/algo_and_ds/algo/counting_sort.html

要素数のカウントに使われているアルゴリズム自体は、Counting Sortの分布数え上げ部分（の応用）を用いている。
それに加えて、カウント前にコストのかかる"分布をチェックする配列(flag)の初期化を省略する"ことによって高速化が実現されている。
ただし、この高速化手法の副作用として、当たり前だけど、flagには"初期状態で何が入っているかわからない"。このため、シンプルにCounting sortを応用したコード（OKWaveの質問者が２番目に上げているコード）のように、flagの値を見るだけでは１度カウントした値かどうかを判断できない。この問題に対する解決策として、１度カウントした値は別の配列(link)に保存し、これを使ってカウントしたかどうかの判定を行っている。このとき、linkは初期化せず、また保持する位置はflagと同じ位置とすることで、余計なコストを発生させずに済んでいる。（と自分は理解しました。）
いや、もうほんと分かった瞬間、目から鱗が落ちた。これ考えた人賢いなぁ。
ただ、残念なことにこの方法言語仕様に依存するので、応用があまり利かないよなぁ…。
ここまで工夫を凝らしたテクニック思いつくのって、「リソースが限られてるけど速度をどうにかしてださないと」ってな状況にいた組み込み系の人、って気がする。なんとなくだけど。