基数整列は、複数桁の数値や文字列を、各桁のバイトを使用して整列するのに用います。各桁が表す整数（文字）のバイトサイズはRadix Rとするため、Radix Sortと呼びます。

基数整列アルゴリズムは、入力桁（ソートキー）をR個に分割するものとします。例えば基数が1バイト(8-bit)であれば、256個に分割します。基数の単位は一般に「Bucket」（バケット）または「Bin」（ビン）と呼称します。

ソートキー内のバイト0

ソートキー内のバイト1

...

ソートキー内のバイトN-1

Bucket[0]

Bucket[1]

...

Bucket[N-1]

基数整列にはMSDとLSDの２種類がありますが、MSD（Most Significant Digit）はソーティングキーを左数えします。反対にLSD（Least Significant Digit）は右からソーティングキーを数えていきます。

基数配列（Radix Sort）の並列化についてはいくつかありますが、一般的な参考文献となる以下のものを使います。

「Radix Sort for Vector Multiprocessors. Marco Zagha, Guy E. Blelloch」

Zagha & Blellochのアルゴリズムは３部で構成されます。

これらのステップは「カウンティングソート」（バケットソートが用いられることもある）に基づいています。

ソート
    // K: 未整列データ
    // N-1: データサイズ
    // D: ソーティングキー
    do j = 0 to N - 1
        D[j] = K[j] & R
    基数キーのヒストグラム
        // R: (2のr乗 - 1)
        do i = 0 to (2のr乗 - 1)
            Bucket[i] = 0
        do j = 0 to N – 1
            Bucket[D[j]] = Bucket[D[j]] + 1 //(1)
    バケットのスキャン（Prefix-Sum）
        Sum = 0
        do i = 0 to 2のr乗 – 1
            Val = Bucket[i]
            Bucket[i] = Sum //(2)
            Sum = Sum + Val
    並び替え
       do j = 0 to N – 1
            A = Bucket[D[j]]
            // R: 整列データ
            // K: 未整列データ
            R[A] = K[j] //(3)
            Bucket[D[j]] = A + 1 //(4)

Note

累積ヒストグラムについての定義は以下の式で表せます。

(1)のnはビン（バケツ）を指し、(2)のMは累積値を示します。