Perlの組み込み関数であるsortは安定なのか？とふと思い、perldocを引いてみる。
perldoc sort
In Perl versions 5.6 and earlier the quicksort algorithm was used to
implement "sort()", but in Perl 5.8 a mergesort algorithm was also made
available, mainly to guarantee worst case O(N log N) behaviour: the
worst case of quicksort is O(N**2). In Perl 5.8 and later, quicksort
defends against quadratic behaviour by shuffling large arrays before
sorting.
ふむ、5.6ではクイックソートだけど、5.8からはマージソートを使っているんですねー。
理由は計算量が最悪の場合でもO(N log N)が保証されているマージソートのほうが良いから、と。
マージソートは安定なソートとしてよく知られていますが、
欠点として、ソート対象と同じ大きさの領域を必要とすることです。
もし、perlでquicksortが使いたい場合、sortを使う前に、
use sort "_quicksort";
とすることで、sortはクイックソートを使うようになります。
安定なソートがどういうときに必要になるか、といえば、
出席番号順に並んだ10人の学生を身長が短い順に並べるとき、
もしある人とある人の同じ身長ならどちらが前になるのか、という問題があります。
安定なソートであれば同じ身長なら出席番号順並ぶことが保証されますが、
安定でないソートならばデータの並び方によって結果が変わります。
それにしてもperldocはたまに面白い事が書いてあって楽しい。暇なときに眺めよう。
