[Issue 14340] AssertError in std.algorithm.sorting: unstable sort fails to sort an array with a custom predicate

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=14340

Xinok <xinok at live.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xinok at live.com

--- Comment #3 from Xinok <xinok at live.com> ---
This is just outright wrong. The sort function was never intended to work in
this way nor is there any reasonable expectation for it to do so either. The
predicate is expected to define a total order [1] which your predicate does
not. To put it in simpler terms, the predicate is expected to return the same
output given the same inputs.

>From a theoretical perspective, this problem is impossible to solve using a
sorting algorithm which runs in polynomial time. In the general case, given a
predicate we know nothing about, the only way to find the correct order (or any
correct order) is to test all permutations which would require O(n!) time. More
importantly, the predicate (really, I should be calling it an invariant) may be
impossible to satisfy meaning there is no solution.

On a side note, for ranges with length <= 25, it bypasses quick sort and jumps
straight into insertion sort. So even if we fix insertion sort to work with
your specific predicate here, given a larger range, it will likely still be
broken.

[1] https://en.wikipedia.org/wiki/Total_order


I won't close this issue but I advise marking this as WONTFIX.

--