[fpc-devel] Sorting tests

[J. Gareth Moreton]

This is why I hope my own improvement to the version in TArrayHelper 
could be used instead:

https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334

Now that I know where Introsort is in the sortalgs.pp unit, I'll see 
about improving Introsort there too.

Regarding a stable sort, what does GCC's "std::stable_sort" use? 
https://www.youtube.com/watch?v=kPRA0W1kECg&t=3m5s - it resembles merge 
sort.  (The algorithm before it in the video, "std::sort", is introsort, 
but it postpones doing the insertion sort until the very end, which 
doesn't work in practice because of caching issues)

Kit

On 29/11/2022 15:03, Stefan Glienke via fpc-devel wrote:
> 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,
>>
>> 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
>> _______________________________________________
>> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
>> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>