Subject: Re: bug#18361: New 'sort' implementation can crash Emacs

From: Paul Eggert <[email-masked]>
Date: Sat, 30 Aug 2014 06:44:54 -0700

Dmitry Antipov wrote:

> couldn't we detect an improper comparison
> function at runtime?

Not easily, because it doesn't suffice to check whether the function is 
antisymmetrical at each comparison (a local property).  One must check 
whether the function defines a total order (a global property).  One way 
to do such a check is to sort the array, and then compare all pairs to 
verify that the function is indeed a total order.  But of course that 
begs the question of sorting the array, plus it's an O(N**2) check, so 
it's not practical.