Pathologically Eclectic Rubbish Lister | |
PerlMonks |
Re^5: Sort mechanics problems ... (efficiency)by tye (Sage) |
on Jun 02, 2016 at 07:32 UTC ( [id://1164739]=note: print w/replies, xml ) | Need Help?? |
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
In Section
Seekers of Perl Wisdom
|
|