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@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
