Gauche のソート
現在の実装では、cmpfnが省略された場合はクィックソートとヒープソートを使い、 cmpfnが与えられた場合はマージソートを使っています。
Gauche Users’ Reference: Top
へー。何かこの挙動の根拠はあるのかしら?
クイックソートとヒープソートをってのはイントロソートのことだと思うんだけど、比較関数が与えられたときにマージソートになるのが気になる。
追記
Shiroさんがタイムリーにお書きになられていた。
ただ、このアルゴリズムは比較関数を省略してデフォルトのを使った場合に限られてて、比較関数を渡した時はSchemeで書かれたMerge Sortになる。 Scheme関数をCからコールバックするオーバヘッドのせいで、pure Schemeの実装の方が速かったからだ。
http://practical-scheme.net/wiliki/wiliki.cgi?Shiro
なるほどー。使うアルゴリズム自体ではなく、どのレイヤで実装されてるかっつう話か。
てことはビルトインの比較を使わないときはSchemeで自前で実装したイントロソートを使うと速くなったりするのかな。