http://d.puremagic.com/issues/show_bug.cgi?id=5514

           Summary: Erroneous documentation and lacking randomization for
                    topN
           Product: D
           Version: unspecified
          Platform: Other
        OS/Version: Mac OS X
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: magnus@hetland.org


--- Comment #0 from Magnus Lie Hetland <magnus@hetland.org> 2011-02-01 07:57:21 PST ---
The topN function in std.algorithm is documented as having a running time of
Ο(r.length), if stable. This should be an *expected* (or average-case) running
time of O(r.length), with a worst-case running time of O(r.length^^2), based on
the current implementation, which is the Randomized-Select algorithm.

Also, the implementation should probably use randomization (as in the standard formulation of the algorithm), rather than consistently picking the middle element. This will entail a slight overhead in picking the pivot, but this will (on average) only be done a logarithmic number of times, so the cost should be negligible. The gain from this is, of course, that consistent worst-case behavior in the face of certain inputs is avoided.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5514


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |andrei@metalanguage.com
         AssignedTo|nobody@puremagic.com        |andrei@metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5514



--- Comment #1 from github-bugzilla@puremagic.com 2013-02-24 16:49:26 PST ---
Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/7291d2e47d4a7fb17565a7d7cd04ba8f893c1a27 issue 5514

https://github.com/D-Programming-Language/phobos/commit/299cf68ecc6ee7e81c1e6a45f747c80b46fa0184 Merge pull request #1167 from andralex/5514

Fix Issue 5514 - Erroneous documentation and lacking randomization for topN

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5514


Alex Rønne Petersen <alex@lycus.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
                 CC|                            |alex@lycus.org
         Resolution|                            |FIXED


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------