• via Digitalmars-d-bugs (22/22) Feb 24 2015 https://issues.dlang.org/show_bug.cgi?id=14223

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

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 puremagic.com
          Reporter: acehreli 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

--