なんか偶然ソートの話になってるけど
流れを読んでからこれ書いたんじゃなくて
「ところでインサーションソートなんてベクタじゃ苦しいだろうけど
リストならすごく効率がいいんではないか？　を確かめようとしたら
list::sortがおそらくすでに十分に効率的に書かれてることが分かって
インサーションソートを自分で実装する気が萎えた
（いちおう拾ったコードは乗せてあるけどクッソ遅い）」という別の話

https://ideone.com/D9ljA7
function asc desc shuf
std::sort(v) 16 13 72
list::sort 43 60 332　←十分早い
std::qsort(v) 47 45 144　←参考