[Issue 14223] TimSort algorithm is incorrect

[via Digitalmars-d-bugs]

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

Ketmar Dark <ketmar at ketmar.no-ip.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ketmar at ketmar.no-ip.org

--- Comment #1 from Ketmar Dark <ketmar at 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.

--