この論文によると、Knuthのgap式よりも性能の良いものがいくつか提案されているようです。その中のTokudaの式を使うことにします。 ■実行結果 確かにKnuthのものより計算量が少なくなっていて、Quick sortと似たような要素数依存性(Ｏ(NlogN))を見せています…