That is not a very good IntroSort to be honest. It is missing using InsertionSort for small numbers and it does not do the median-of-3 pivot selection.

Am 29.11.2022 um 09:22 schrieb Nikolay Nikolov via fpc-devel:

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,


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).


fpc-devel maillist  -
fpc-devel maillist  -
fpc-devel maillist  -

Reply via email to