Generally, sort functions are designed to do sorting as efficiently as possible, typically in O(n log(n)) comparisons. I'm not aware of any way to force perl's sort to do all n(n - 1) / 2 comparisons: if the purpose is not sorting, best not use sort() to do it.

The results from the comparator are intended to describe an ordering on the elements: compare(A, B) < 0 asserts that A < B, etc. There is an expectation of consistency here, so we expect identities like these to hold:

A = A
A = B  <=>  B = A
A < B  <=>  B > A
A <= B  <=>  B >= A
(A < B) & (B < C)  =>  A < C
(A <= B) & (B <= C)  =>  A <= C
[download]

Note this important paragraph skulking near the end of perldoc -f sort:

            The comparison function is required to behave. If it retur
+ns
            inconsistent results (sometimes saying $x[1] is less than 
+$x[2]
            and sometimes saying the opposite, for example) the result
+s are
            not well-defined.
[download]

For a bit more about what can go wrong, see the accepted response on this related C++ question: What will std::sort do if the comparison is inconsistent?. I'm not aware that perl's implementation is at risk of crashing, but you are certainly entitled to get weird results.