The problem with sample code that is already wrong is that it night have a different problem from the same theoretical weakness. So the issue of circular dependencies should be resolved in theory before writing any more code.

Even if we discuss theory, you still need to communicate the potential problem somehow. So I disagree that code isn't useful at this point - it should be possible to construct a piece of sample code that demonstrates the infinite loop issue that you are worried about, even if it takes one or two iterations.

Regards,
-- Hauke D

Sometimes you have to be careful what you wish for. The following test code should produce an infinite loop (because there is no documented alternative):

#!/usr/bin/perl 

use strict;
use warnings;

my $iteration = 0;
print sort byStupid (qw(A B C));

sub byStupid {
    $iteration++;
    $iteration > 10000 and die "10000 is a lot to sort three things";
    if ($b eq 'C' and $a eq 'A') {
    $b cmp $a;
    }
    else {
    $a cmp $b;
    }
}
[download]

Unfortunately perl sort is content to produce incorrect output in finite time. i.e. it chose to ignore the correct positioning of B and C in the list and produced CAB as output. The correct behaviour would be an infinite loop or a fatal error because the array in any order is an incorrectly returned result from function 'sort'.

One world, one people

No.

As documented, the results are "not well-defined". It is far better for a sort algorithm to not go into an infinite loop. Sort algorithms are heavily optimized (for good reasons) to do as few comparisons as possible. Those optimizations are predicated on the assumption that you actually have a well-ordered set with a well-defined comparison operation. Because that is what people generally have when they call an optimized 'sort'.

The good sorting algorithms are so optimized that they are actually unable to even notice that your comparison operation is not well-defined. If a 'sort' sees $a < $b, then it would be a waste of resources if it later needed to check if $b < $a. So efficient sorting algorithms never do that. If they even see $a < $b and $b < $c, then they also won't bother comparing $a to $c.

If you want some kind of 'sort' that is guaranteed to detect the well-definedness of the comparison, then that 'sort' will always be O(n*n), no matter the input.

But even if you had one of those, having one that can go into an infinite loop would just be stupid. That only makes even a little sense if checking $a < $b a second time might give you a different answer than the first time. And if that really matters to you, then your 'sort' can never ever return, because just because $a < $b the first 10,000 times you checked, it might not stay that way.

- tye        

Thank you for the clarification! It was unclear to me at first if maybe it was some kind of infinite recursion problem, but I see now what you mean. As tye has already explained, the answer is clear: a comparator like that means the result of the sort is not well-defined.

Although I think in this case a solution other than sort is more appropriate, just to play out the idea in theory: If you wanted to sort by changing criteria, including criteria based on the position of each item in the list, then something resembling an iterative approach might be possible: 1. calculate and cache the sort criteria, 2. run the sort, 3. check if the ordering is appropriate and if not go back to step 1. That way, you're not violating the requirements of sort (the criteria remain stable during the entire run of sort), although you do have the problem that the algorithm might not converge overall.

Regards,
-- Hauke D