逆写像ソート - abwiki @ ウィキ (ActiveBasic非公式wiki)

整列アルゴリズムのひとつ。
分布数えソートと同じく実行時間は O(n) であり安定であるが、分布数えソートよりも若干遅いようである。整列に使用するキー値は一定の範囲の整数でなければならない。アルゴリズムは以下のとおり。
x = a[i] ⇔ i = index[x] となる index[x] を作成する
もし x = a[i] となる i がなければ index[x] = -1とする
キー値が重複する場合、別配列 next[i] を用いてその並びを記述する（ex：a[i] = a[j] = a[k] ⇒ next[i] = j, next[j] = k, next[k] = -1）
index[x] <> -1のとき、a[index[x]] を書き出す

プログラミング掲示板「ソートロジック大会」なども参照のこと

Const MAX = 100
Const MIN = 0
Sub mapsort(n As Integer, a As *Integer, b As *Integer, next As *Integer)
Dim i As Integer, j As Integer, x As Integer
Dim index[MAX - MIN + 1] As Integer
' index[]の初期化
For x = 0 To MAX - MIN
index[x] = -1
Next x
' index[]の作成
For i = n To 0 Step -1
x = a[i] - MIN
next[i] = index[x]
index[x] = i
Next i
' データの書き出し
j = 0
For x = 0 To MAX - MIN
i = index[x]
While i >= 0
b[j] = a[i]
j = j + 1
i = next[i]
Wend
Next x
End Sub