How so? Heapsort isn't stable either. Is there a variant I'm not aware of?
Kit
On 29/11/2022 16:36, Marco van de Voort via fpc-devel wrote:
On 29-11-2022 17:34, J. Gareth Moreton via fpc-devel wrote:
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)
Usually it is heapsort that is picked as alternative to quicksort if
stable algo is needed.
_______________________________________________
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