ラディックス・ソート - abwiki @ ウィキ (ActiveBasic非公式wiki)

整列アルゴリズムのひとつ。
基数（radix）ソートとも呼ばれ、キーを桁ごとに処理していく整列法である。キーの桁数をm桁としたときの実行時間は O(m×n) と高速であり、また安定でもある。

入力データは、数字の桁数や文字列の文字数などキーの形式が定まっていることを前提とし、また各桁の処理に実行時間 O(n) である整列法（分布数えソートなど）を使用することから有限かつ最大・最小値の定まったものを必要とする。 そのアルゴリズムは以下のとおり。
入力データは、桁数ごとのキーに分類する。3桁の数字であれば、1の位・10の位・100の位など。
それぞれのキーについて、下位のキーから整列する。ここでの整列法の実行時間および安定性がラディックス・ソートのそれに影響する。
ここでは最速かつ安定であることを目指すことから、分布数えソートを使用する。 桁数が多いときでも、数桁をラディックス・ソートで整列し、仕上げを挿入ソートにするなどできる。

下記プログラムでは、原著に近い形のデータ構造として、Byte型配列（数値ないし文字列）のポインタを格納したDWord型配列とした。

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

Const UCHAR_MAX = 255
Sub radixsort(n As Integer, length As Integer, a As *DWord, work As *DWord)
Dim i As Integer, j As Integer
Dim count[UCHAR_MAX] As Integer
Dim pByte As *Byte
' 桁数分繰り返し
For j = length - 1 To 0 Step -1
'初期化
For i = 0 To UCHAR_MAX
count[i] = 0
Next i
'出現文字のカウント
For i = 0 To n
pByte = a[i]
count[pByte[j]] = count[pByte[j]] + 1
Next i
'並び替えの位置決め
For i = 1 To UCHAR_MAX
count[i] = count[i] + count[i - 1]
Next i
'並び替え
For i = n To 0 Step -1
pByte = a[i]
count[pByte[j]] = count[pByte[j]] - 1
work[count[pByte[j]]] = a[i]
Next i
For i = 0 To n
a[i] = work[i]
Next i
Next j
End Sub