[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

Ivan Kazmenko <gassa at mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|major                       |critical

--- Comment #1 from Ivan Kazmenko <gassa at mail.ru> ---
The culprit is optimisticInsertionSort.

When the range hasAssignableElements, it changes the array too heavily while
calling the predicate:

https://github.com/D-Programming-Language/phobos/blob/4abe95ef/std/algorithm/sorting.d#L799-L806

The problem is:

1. The predicate (count) depends on array integrity (order does not matter,
contents do) at all times it is called.

2. The library is too optimistic taking an element to a temporary variable and
then overwriting the elements, all the way calling the predicate.

I'm unsure what should be done.

On one hand, the user has the right to abstract away from sort implementation.

On the other hand, the speedup for a range which hasAssignableElements may be
significant for more trivial cases.

I'd suggest to be on the safe side.  First, find the greatest value of j using
pred, just like now:
-----
for (; j < maxJ && pred(r[j + 1], temp); ++j) {}
-----

Only after that, perform all swaps:
-----
auto temp = r[i];
for (size_t k = i; k < j; ++k)
{
    r[k] = r[k + 1];
}
r[j] = temp;
-----

After all, the last thing one wants is a failing library sort function, no
matter how weird its usage may be.

Another solution would be to note in the documentation that, with unstable
sort, the predicate must not depend on the range.  But most users won't care to
read or remember that unless the sort goes wrong.

Ivan Kazmenko.

--