← Back to index
|
Original Bugzilla link
Bug 14223 – TimSort algorithm is incorrect
Status
RESOLVED
Resolution
FIXED
Severity
normal
Priority
P1
Component
phobos
Product
D
Version
D2
Platform
All
OS
All
Creation time
2015-02-24T21:34:00Z
Last change time
2017-07-19T17:42:19Z
Assigned to
nobody
Creator
acehreli
Comments
Comment #0
by acehreli — 2015-02-24T21:34:38Z
The following article describes and proposes a fix for a common bug in the TimSort algorithm:
http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
ketmar agrees that Phobos's version of TimSort has the same bug:
http://forum.dlang.org/thread/
[email protected]
#post-mciit8:242dvo:24102:40digitalmars.com
Ali
Comment #1
by ketmar — 2015-02-24T21:48:10Z
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.
Comment #2
by github-bugzilla — 2015-03-14T06:31:01Z
Commits pushed to master at
https://github.com/D-Programming-Language/phobos
https://github.com/D-Programming-Language/phobos/commit/323b512596470227893f3682474db2b4df36a673
Fix Issue 14223
https://github.com/D-Programming-Language/phobos/commit/4abe95ef5b9f67ae072147befdda9200aa0c2061
Fix Issue 14223
https://github.com/D-Programming-Language/phobos/commit/35bf4918ccbb5e3e1cdaf38e84d1d19b5365045d
Merge pull request #3029 from Xinok/issue_14223 Fix Issue 14223 - TimSort algorithm is incorrect
Comment #3
by github-bugzilla — 2015-06-17T21:03:16Z
Commits pushed to stable at
https://github.com/D-Programming-Language/phobos
https://github.com/D-Programming-Language/phobos/commit/323b512596470227893f3682474db2b4df36a673
Fix Issue 14223
https://github.com/D-Programming-Language/phobos/commit/4abe95ef5b9f67ae072147befdda9200aa0c2061
Fix Issue 14223
https://github.com/D-Programming-Language/phobos/commit/35bf4918ccbb5e3e1cdaf38e84d1d19b5365045d
Merge pull request #3029 from Xinok/issue_14223
Comment #4
by github-bugzilla — 2017-07-19T17:42:19Z
Commits pushed to dmd-cxx at
https://github.com/dlang/phobos
https://github.com/dlang/phobos/commit/323b512596470227893f3682474db2b4df36a673
Fix Issue 14223
https://github.com/dlang/phobos/commit/4abe95ef5b9f67ae072147befdda9200aa0c2061
Fix Issue 14223
https://github.com/dlang/phobos/commit/35bf4918ccbb5e3e1cdaf38e84d1d19b5365045d
Merge pull request #3029 from Xinok/issue_14223