On Fri, 12 Jan 2018, Jeff Law wrote: > THe key here is the results can differ if the comparison function is not > stable. That's inherent in the qsort algorithms.
I'm afraid 'stable' is unclear/ambiguous in this context. I'd rather say 'if the comparator returns 0 if and only if the items being compared are bitwise identical'. Otherwise qsort, not being a guaranteed-stable sort, has a choice as to how reorder non-identical items that compare equal. > But, if the comparison functions are fixed, then the implementation > differences between the qsorts won't matter. > > Alexander Monokov has led an effort to identify cases where the > comparison functions do not provide a stable ordering and to fix them. No. The qsort_chk effort was limited to catching instances where comparators are invalid, i.e. lack anti-commutativity (may indicate A < B < A) or transitivity property (may indicate A < B < C < A). Fixing them doesn't imply making corresponding qsort invocations stable. > Some remain, but the majority have been addressed over the last year. > His work also includes a qsort checking implementation to try and spot > these problems as part of GCC's internal consistency checking mechanisms. Well, currently qsort_chk only checks for validity. It could in principle check for stability, but for each unstable sort it's rather hard to analyze whether it may ultimately cause codegen changes, and as a result patches may be impossible to justify. Alexander
