https://issues.dlang.org/show_bug.cgi?id=14223
Ketmar Dark <ket...@ketmar.no-ip.org> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |ket...@ketmar.no-ip.org --- Comment #1 from Ketmar Dark <ket...@ketmar.no-ip.org> --- a possible patch: fixes TimSort implementation, according to http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ diff --git a/std/algorithm/sorting.d b/std/algorithm/sorting.d index a71eb47..f40e957 100644 --- a/std/algorithm/sorting.d +++ b/std/algorithm/sorting.d @@ -1230,21 +1230,21 @@ private template TimSortImpl(alias pred, R) while (stackLen > 1) { immutable run3 = stackLen - 1; - immutable run2 = stackLen - 2; + auto run2 = stackLen - 2; immutable run1 = stackLen - 3; - if (stackLen >= 3 && stack[run1].length <= stack[run2].length + stack[run3].length) + immutable run0 = stackLen - 4; + if ((stackLen >= 3 && stack[run1].length <= stack[run2].length + stack[run3].length) || + (stackLen >= 4 && stack[run0].length <= stack[run2].length + stack[run1].length)) { - immutable at = stack[run1].length <= stack[run3].length - ? run1 : run2; - mergeAt(range, stack[0 .. stackLen], at, minGallop, temp); - --stackLen; + if (stack[run1].length < stack[run3].length) + --run2; } - else if (stack[run2].length <= stack[run3].length) + else if (stackLen < 2 || stack[run2].length > stack[run3].length) { - mergeAt(range, stack[0 .. stackLen], run2, minGallop, temp); - --stackLen; + break; // invariant is established } - else break; + mergeAt(range, stack[0 .. stackLen], run2, minGallop, temp); + --stackLen; } } i haven't analyzed the code, though, and didn't run any unittests besides the simplest ones, so i can't guarantee that i did it right. so hereby i sommon someone more knowledgeable to properly check it. --