イントロソート
ちとメモ
イントロソート（英: introsort）は、David Musser が1997年に設計したソートアルゴリズムである。最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。
Shiro:log:2008前半の2008/06/06らへんより。
Gaucheの組み込みの(Cで実装された)ソートはデフォルトではQuick Sortで始めて、再帰の深さが ceiling(2*log(N)) を越えた時にHeap Sortにスイッチするようにしてる。この技は(もう覚えてないけど、コメントによれば)TAOCPに出ていたようだ。 Quick SortもHeap Sortもin-placeでできるので、既にQuick Sortでソート済みの連続領域がいくつかある状態でそれぞれの領域にそのままHeap Sortを適用できるのは便利。
コレダ。
