Skip to content

Improve NaturalCompareText behaviour as a comparer.

Rika requested to merge runewalsh/source:natural into main

Merge request for #39951.

NaturalCompareText is somewhat flawed, being able to return garbage or intransitive results. Intransitivity can result in a crash if the algorithm relied on mathematical properties of the comparison; for example, PDQSort uses special “unguarded” versions for all subranges but the leftmost that don’t check their left boundaries, reasonably assuming that there is an element to the left and that after partitioning it can’t be greater than anything to the right.

Test (with examples from #39951 and some fuzzing that tries to search for intransitiveness :): NaturalCompareText.pas.

Edited by Rika

Merge request reports