# 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 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.

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

- 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):