1.データの中央を基準値にします。
2.基準値より小さいデータ、同じデータ、大きいデータの個数を数えます。
小さいデータ 9
同じデータ 3
大きいデータ 8
3.各データの個数から、それぞれのデータを格納する先頭の位置を計算します
テンポラリー配列
4.配列の先頭からデータを読み、各格納位置へデータをコピーします。
すると、テンポラリー配列上に、基準値を境にして、小さいデータと大きいデータを分けることができます。
5.同じデータに関しては、ソート済みとし、テンポラリー配列に配置されている分は、メインの方にコピーします
小さいデータ、大きいデータの部分に関して再帰的にソートの処理を行います。
今度は、テンポラリー上に配置されたデータを、データ配列に向けてコピーします。
以降、データ配列->テンポラリー配列、テンポラリー配列->データ配列を繰り返す。
※1 未ソート部の個数が1つの場合は、ソート済みと判断します。