glibcのqsort()はクイックソートではない

クイックソートの最悪ケースの実証しようかなーと思ってglibcのソースを見たらクイックソートじゃなかった。

まだちゃんとは読んでないが、次のような仕様ではないかと思われる。

• まず、必要な一時領域のサイズを決定する。
  • 通常は元の配列と同じ。(nmemb * size)
  • sizeが32bytesより大きい場合は間接ソートを行うので、2*nmemb*sizeof(void*)+s必要。
• 一時領域を確保する。
  • 一時領域が1024bytesより小さい場合はスタックから確保(alloca)する。
  • そうでなければmallocを試みる。
  • 必要量がページサイズの1/4以上であるか、mallocに失敗した場合は、一時領域を必要としないクイックソートに切り替える。
• 一時領域の確保に成功したら、マージソートを行う。

glibcのソースのstdlib/msort.cより。