>>525
挿入ソートの場合は、挿入すべき場所に直接挿入すればよいので、
swapで何度も入れ替えないようにして、必要なところに直接挿入するのがいいかもしれません。
一瞬バブルソートのように見えて、挿入ソートってこんなのだっけ？と思いました。

最適化についてはこのコードだけではなんともいえませんが、
大まかでよいのであれば、全体をclock関数で時間計測したように
この関数の中で経過時間を計測してみるのもよいと思います。
効果のある場所が限定できると推測もしやすくなりますので。