[fpc-devel] Sorting tests

J. Gareth Moreton gareth at moreton-family.com
Tue Nov 29 21:16:16 CET 2022

On 29/11/2022 20:03, Nikolay Nikolov via fpc-devel wrote:
> if (a<b) and (b<c) then (a<c),

That's the big one that sorting algorithms rely on... the transitive 
law.  If that is violated, then you cannot guarantee a sorted result.

It doesn't matter if (a < b) or (b < a) return False for equal elements, 
or use (a <=b) or (b <= a) instead, as long as it's consistent.  Also 
have to watch out for more subtle instances of it, like "if (a < b) then 
DoX else DoY;" and then having "if (b < a) then DoZ else DoQ;".

While I do wish people would fix any bugs that are found in their own 
code, sometimes we do have to accept that this isn't always possible.  I 
think the most famous example I can think of is with SimCity 2000... 
there was a critical bug in it where memory was used after it was 
deallocated.  Under DOS and Windows 3.1, this wasn't an issue because 
the memory wouldn't be reused by another application, but under Windows 
95 this assumption could no longer hold.  So, under the guidance of 
Raymond Chen, Microsoft programmed Windows 95 to delay actually 
releasing that block of memory... only for SimCity 2000!


More information about the fpc-devel mailing list