5.6まではクイックソート、5.7からはマージソートみたいです。
$ perldoc -f sort
...
Perl 5.6 and earlier used a quicksort algorithm ...
In 5.7, the quicksort implementation was replaced with a stable mergesort algorithm...
...
何かまずいの??と言われればマージソートは安定だけどクイックソートは非安定、ということです。非安定なソートアルゴリズムはソート前の並びを保持しないので複合型に対するソート結果が変わってきます。
例として・・・
[1,'c'], [5,'b'], [3,'a'],...みたいな数字と文字のセットの配列を考えます。まず文字をキーにソートして、続いて数字でソートするとどうなるでしょうか。
テストスクリプト
srand 1; ## @arr = ([1,c], [5,b], [3,a], ...) push @arr, [(1..5)[rand 5], (a..z)[rand 5]] for 1..10; print "before ...\n"; print join(', ', map "[@$_]", @arr)."\n"; ## まずはアルファベットでソート @arr = sort {$$a[1] cmp $$b[1]} @arr; ## 続いて数字でソート @arr = sort {$$a[0] <=> $$b[0]} @arr; print "sort ...\n"; print join(', ', map "[@$_]", @arr)."\n";
結果
$ perl5.8.8 sort.pl before ... [1 c], [5 b], [3 a], [1 e], [4 b], [2 c], [1 a], [5 a], [3 b], [5 a] sort ... [1 a], [1 c], [1 e], [2 c], [3 a], [3 b], [4 b], [5 a], [5 a], [5 b] $ perl5.6.2 sort.pl before ... [1 c], [5 b], [3 a], [1 e], [4 b], [2 c], [1 a], [5 a], [3 b], [5 a] sort ... [1 c], [1 a], [1 e], [2 c], [3 b], [3 a], [4 b], [5 a], [5 b], [5 a]
[1 a], [1 c], [1 e] と [1 c], [1 a], [1 e]を比べてもらえば一目瞭然。
5.8.8ではアルファベット順が保持されてますが5.6.2だとグチャグチャです。
じゃどうすれば?と言われればこの例では簡単。1回で両方比較してやればいいだけです。
srand 1; push @arr, [(1..5)[rand 5], (a..z)[rand 5]] for 1..10; print "before ...\n"; print join(', ', map "[@$_]", @arr)."\n"; ## まず数値を比較、同じなら文字を比較 @arr = sort {$$a[0] <=> $$b[0] or $$a[1] cmp $$b[1]} @arr; print "sort by alpha and number ...\n"; print join(', ', map "[@$_]", @arr)."\n";
$ perl5.8.8 sort.pl before ... [1 c], [5 b], [3 a], [1 e], [4 b], [2 c], [1 a], [5 a], [3 b], [5 a] sort by alpha and number ... ... [1 a], [1 c], [1 e], [2 c], [3 a], [3 b], [4 b], [5 a], [5 a], [5 b] $ perl5.6.2 sort.pl before ... [1 c], [5 b], [3 a], [1 e], [4 b], [2 c], [1 a], [5 a], [3 b], [5 a] sort by alpha and number ... ... [1 a], [1 c], [1 e], [2 c], [3 a], [3 b], [4 b], [5 a], [5 a], [5 b]
ちなみに他の言語は例えばこんな感じです。
- Cのqsort()はクイックソート
- C++のSTLのsort()はクイックソート、stable_sort()はマージソート
- JAVAのjava.util.Arrays.sort()はプリミティブ型の場合はクイックソート、オブジェクトの場合は安定なマージソート
メモリ容量の増大と(マージソートの欠点はメモリを食うこととされてました)、ソート対象がオブジェクトなどの複合型になるにつれてクイックソートからマージソートに移り変わってきてるみたいですね。