Re: sort question
 From: Nick Wedd <nick@xxxxxxxxxxxxx>
 Date: Sun, 22 Feb 2009 23:26:30 +0000
In message <Xns9BBAAF54BFFC0asu1cornelledu@xxxxxxxxx>, A. Sinan Unur <1usa@xxxxxxxxxxxxxxxxxxx> writes
Nick Wedd <nick@xxxxxxxxxxxxx> wrote in
news:qE51cBBk2boJFAaq@xxxxxxxxxxxxxxxxxxx:
This is exactly what I hoped for. In fact it is better (more useful
to me) than I feel I have any right to expect. When it sorts on one
criterion, it leaves the items that tie under that criterion in the
order they were in before.
Now this is exactly what I want it to do. But no documentation that I
can recall promises that it will do that.
Which version of Perl are you using?
Version 5.6.1
http://perldoc.perl.org/functions/sort.html
So what I am looking for is a "stable" sort. Knowing what it is called will make further investigations easier for me.
That page tells me that the sort in 5.6 is not stable; the one in 5.7 is stable; and in 5.8 I can use a pragma to ensure that it uses a stable sort. So I have been lucky so far, maybe because my arrays have never had more than seven elements.
Perl 5.6 and earlier used a quicksort algorithm to implement sort. That
algorithm was not stable, and could go quadratic. (A stable sort
preserves the input order of elements that compare equal. Although
quicksort's run time is O(NlogN) when averaged over all arrays of length
N, the time can be O(N**2), quadratic behavior, for some inputs.) In
5.7, the quicksort implementation was replaced with a stable mergesort
algorithm whose worstcase behavior is O(NlogN). But benchmarks
indicated that for some inputs, on some platforms, the original
quicksort was faster. 5.8 has a sort pragma for limited control of the
sort. Its rather blunt control of the underlying algorithm may not
persist into future Perls, but the ability to characterize the input or
output in implementation independent ways quite probably will. See sort.
http://perldoc.perl.org/sort.html
use sort 'stable'; # guarantee stability
 Sinan
Thank you.
Nick

Nick Wedd nick@xxxxxxxxxxxxx
.
 References:
 sort question
 From: Nick Wedd
 Re: sort question
 From: A. Sinan Unur
 sort question
 Prev by Date: Re: sort question
 Next by Date: Re: utf8 and chomp
 Previous by thread: Re: sort question
 Next by thread: Re: sort question
 Index(es):
Relevant Pages
