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
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?
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 worst-case 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.
use sort 'stable'; # guarantee stability
Nick Wedd nick@xxxxxxxxxxxxx