qnighy https://blog.hatena.ne.jp/qnighy/ 簡潔なQ https://qnighy.hatenablog.com/ Programming C クイックソートの最悪ケースの実証しようかなーと思ってglibcのソースを見たらクイックソートじゃなかった。まだちゃんとは読んでないが、次のような仕様ではないかと思われる。 まず、必要な一時領域のサイズを決定する。 通常は元の配列と同じ。(nmemb * size) sizeが32bytesより大きい場合は間接ソートを行うので、2*nmemb*sizeof(void*)+s必要。 一時領域を確保する。 一時領域が1024bytesより小さい場合はスタックから確保(alloca)する。 そうでなければmallocを試みる。 必要量がページサイズの1/4以上であるか、mallocに失敗した場合は、一… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fqnighy.hatenablog.com%2Fentry%2F20090430%2F1241054709" title="glibcのqsort()はクイックソートではない - 簡潔なQ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-04-30 10:25:09 rich https://qnighy.hatenablog.com/entry/20090430/1241054709 1.0 100%