Re: sort question

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?

Version 5.6.1

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

-- Sinan

Thank you.

Nick Wedd nick@xxxxxxxxxxxxx

Relevant Pages

  • Re: sort question
    ... criterion, it leaves the items that tie under that criterion in the ... Perl 5.6 and earlier used a quicksort algorithm to implement sort. ...
  • Re: sort on third, then second field
    ... > A. Sinan Unur wrote: ... I am trying to get this to sort by date (third field) then ... Because of the stable sort ...
  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... I would tailor which algorithm to start with by how the student thinks ... If you only learn the beautiful side of programming, ...
  • Re: puzzle
    ... >> Christopher Barber wrote: ... >> or understanding among programming professionals. ... > algorithm "close to" O. ... bubble sort, it is almost always acceptable to use an interchange sort: ...
  • Re: Shocking mistake with comparitor function by Microsoft programmers!
    ... Well, I already got a very similar discussion with Pete, but ASSUMING the classic quick sort algorithm: ... The transitivity is not required by virtue of the partitions: those less than the pivot are in a partition which won't speak to those values that were greater to the pivot, since those are in another partition, and elements of different partitions would not be involved between themselves. ... The reflexivity rules are not required either since the pivot won't be compared, a second time (in the classic quick sort algorith). ...