[fpc-devel] Sorting tests

[J. Gareth Moreton]

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