From:

Date:

September 22, 2006 06:40Subject:

sort and 0 returns from comparison routinesMessage ID:

mid+200609221345.k8MDjvBH1238267@dogberry.rutgers.eduIt is possible for there to be two different meanings for a 0 return from a comparison routine for sort, but sort assumes (as far as I can tell) that the first is correct: A. $a and $b are equal; B. The ordering of $a and $b cannot be determined from $a and $b alone. The latter situation can come up in, for instance, phylogenetics and taxonomy, which is what I have been working on. It may be possible for a comparison routine to return that X is greater than Y (e.g., X is the parent of Y), and that Y is greater than Z, but it may not be (conveniently) possible for the comparison routine to determine that X is greater than Z (e.g., because it would have to check all the descendents of X). Two questions: A. Does anyone know of a sort algorithm (preferably conveniently implementable in Perl or puttable in as an alternative to the current mergesort/quicksort choice) that would be able to recognize the above (perhaps with a return from the comparison routine of undef instead of 0, if such a distinction was necessary?)? B. With regard to perl's currently available mergesort/quicksort choice, which is more likely to handle this sort of situation (in which one may get seemingly inconsistent results from a comparison routine - of X vs Y being 1 and Y vs Z being 1 but X vs Z being 0) as desired? If this can be determined, it would be helpful to have this in the manpage for the sort pragma. Likewise, documentation of what happens (for each of mergesort and quicksort) if a comparison routine is _actually_ inconsistent would be helpful. Thanks, -Allen -- Allen Smith http://cesario.rutgers.edu/easmith/ There is only one sound argument for democracy, and that is the argument that it is a crime for any man to hold himself out as better than other men, and, above all, a most heinous offense for him to prove it. - H. L. MenckenThread Next

**sort and 0 returns from comparison routines**by Allen Smith- Re: sort and 0 returns from comparison routines by John P. Linderman

nntp.perl.org: Perl Programming lists via nntp and http.

Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About