[fpc-devel] Sorting tests

[Nikolay Nikolov]

On 11/24/22 20:51, J. Gareth Moreton via fpc-devel wrote:
> Hi everyone,
>
> I just need to touch on the knowledge base.  What tests exist that 
> test the functionality of rtl/inc/sortbase.pp?  As Olly suggested, I'm 
> looking at creating Introsort for this unit as well, but I need to 
> know if such a unit already exists or if I need to make my own.

But IntroSort is already implemented in 
packages/rtl-extra/src/inc/sortalgs.pp. It's just not the default 
sorting algorithm, because it breaks existing code that implements an 
incorrect comparison function. E.g. if you pass a function that returns 
a<b=true and b<a=true, or a<b=false and b<a=false, the behavior will 
change, when you change the algorithm. This even broke Lazarus, it 
caused it to hang on startup.

Best regards,

Nikolay

>
> Also, since Olly mentioned that the unit is used in TStringList, it 
> makes me wonder if the RTL has a radix sort algorithm available, since 
> radix sort is on the order of O(n) and is ideal for sorting large 
> arrays of strings (although it can be memory-intensive).
>
> Kit
>
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel