[Issue 14223] New: TimSort algorithm is incorrect

via Digitalmars-d-bugs digitalmars-d-bugs at puremagic.com
Tue Feb 24 13:34:38 PST 2015


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

          Issue ID: 14223
           Summary: TimSort algorithm is incorrect
           Product: D
           Version: future
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P1
         Component: Phobos
          Assignee: nobody at puremagic.com
          Reporter: acehreli at yahoo.com

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/mcigvq$11p0$1@digitalmars.com#post-mciit8:242dvo:24102:40digitalmars.com

Ali

--


More information about the Digitalmars-d-bugs mailing list