qsort - enbug diary (2007-02-10)_ qsort ちょっと古いスレッドだが、 Slow glibc qsort, two versions that are much faster という話題があった。 要するに、glibcのqsortは遅くて、 qsortG やNetBSDのqsortは速いとか。 ほんまかなーと思って、ちょっと試してみた。 intの配列一千万個で、 ランダム、ソート済み、大体ソート済み、逆順を対象に、 glibcのqsort、qsortG、 STLのsort でまず実験。 glibcのqsortはメモリを確保できそうな大きさなら mergesortで、 そうでないと quicksort である。 qsortGはひらすらquicksort、 STLはSGI STL由来だから、 多分 introsort で、 quicksort + heapsort + insertion sort のはず。 ところが、q
