Bug 5514 – Erroneous documentation and lacking randomization for topN

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.

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