ウィキペディア

イントロソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2009/06/12 02:22 UTC 版)

イントロソート（英: introsort）は、David Musser が1997年に設計したソートアルゴリズムである。最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。クイックソートもヒープソートも比較ソートであり、イントロソートも同様である。