>>130
qsort の方はよく知らんが、STL の方は、

基本はクイックソート
pivot には先頭・ど真ん中・末尾の要素の中央値を使う
要素数が小さくなってきたら挿入ソートに切り替える
あと、最新版では再起が深くなってきたらマージソートに切り替えるって機能も付いてたと思われ。