[Issue 7767] New: Unstable sort - slow performance cases

[d-bugmail at puremagic.com]

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

           Summary: Unstable sort - slow performance cases
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: xinok at live.com


--- Comment #0 from Xinok <xinok at live.com> 2012-03-24 20:00:28 PDT ---
I've discovered a number of cases in which the unstable sort in std.algorithm
performs very poorly. I'll provide the simplest example I have.

import std.stdio, std.algorithm, std.range, std.datetime;
void main(){
    uint[] arr;
    arr.length = 1024 * 1024;
    foreach(i, ref v; arr) v = i;
    swapRanges(arr[0..$/2], arr[$/2..$]);
    StopWatch sw;
    sw.start();
    sort(arr);
    sw.stop();
    writeln(sw.peek.seconds, " seconds");
}

This case takes 28 seconds on my PC. The problem can be solved by falling back
to a heap sort or shell sort after so many recursions. Slow cases like these
have possible security implications.

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