Perl Sort Unstable

Xah Lee, 2012-12-30

One piece of history. Perl's “sort” function used to be unstable. That is, it messes up your original order.

Here's one of my old note in perl:

# -*- coding: utf-8 -*-

# date: 2005
# perl's sort f�cking messes up the original order. This is typical of things in Perl and Perl people.
# this is fixed sometimes after 2005.

use Data::Dumper;
$Data::Dumper::Indent=0;

@aa = ([4,3],[1,3],[3,28],[2,3],[5,2],[6,1]);

@bb = sort {$a->[1] <=> $b->[1]} @aa;

print Dumper \@bb;

It sorts list of pairs by their second element. Normally, the first 2 elements [4,3],[1,3] should remain in that order. But if it's unstable, it changes their order.

Here's verification. From perl 5.8.6 history file. Perl 5.8.6 is released on 2004-11-27.

Although Perl has promised since version 5.8 that sort() would be stable, the two cases sort {$b cmp $a} and sort {$b <=> $a} could produce non-stable sorts. This is corrected in perl5.8.6.

from http://perldoc.perl.org/perl586delta.html