前回で終わりのような気がしていたが別にそんなことはなかったぜ！
今まで紹介したシェアソートは要素の数が平方数でした。
サンプルなので奇麗に正方形に並べられる個数ばかり選んでたわけです。
シェアソートは矩形(長方形)に並べられれば良いのですが、
要素の数が素数だった場合はそれすら適いません。
ということでそんな半端の状態のシェアソートです。
39個の要素でシェアソートを行おうとすると、以下のようになります。
実は、この形でも以下のように分割してシェアソートを行えば問題がありません。
豆知識として、縦ソートをするときに40以上の位置を差したら終端としておくと、
どこで数が変わったかというのを意識しないで済みます。
ですが、折り返しで終わった場合はちょっと工夫が必要です。
以下のような場合ですね。
空白に最大値を入れてソートでも良いのですが、スマートではないです。
そこで、1行6個ではなく7個で作りなおしてみます。
うまく行きました。
ちょうどいい一行の数の求め方ですが、今回はこうやっています。
44 ÷ 6 = 7 余り 2
1行6個で並べれば7行と2個と読めますが、
逆に1行7個で並べれば6行と2個という読み方をします。
適当な偶数で割ってやってその商を1行の個数とすれば
必ず都合のいい配置になってくれるわけです。