[LLVMbugs] [Bug 20837] New: libc++ std::sort has O(n^2) worst case, standard mandates O(N log(N))

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=20837

            Bug ID: 20837
           Summary: libc++ std::sort has O(n^2) worst case, standard
                    mandates O(N log(N))
           Product: libc++
           Version: unspecified
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: orsonpeters at gmail.com
                CC: llvmbugs at cs.uiuc.edu, mclow.lists at gmail.com
    Classification: Unclassified

Created attachment 12978
  --> http://llvm.org/bugs/attachment.cgi?id=12978&action=edit
Evidence for quadratic worst case.

The C++ standard mandates that `std::sort` has complexity O(N log(N)), but
libc++'s implementation takes O(N^2) in the worst case.

As proof I've attached a program that constructs a worst case input for several
sizes. It also instruments the number of comparisons used to sort these worst
cases and prints the results. The technique used is described in the 1999 paper
"A Killer Adversary for Quicksort" by M. D. McIlroy.

Compiling and running:

$ clang++ -O2 -m64 -march=native -std=c++11 -stdlib=libc++ main.cpp
-nodefaultlibs -lc++ -lc++abi -lm -lc -lgcc_s -lgcc && ./a.out
N: comparisons
100: 2479
200: 10229
400: 40729
800: 161729
1600: 448698
3200: 1413898
6400: 5264298

This is clearly quadratic. To illustrate this defect more, these are the
comparison counts given by compiling using libstdc++:

$ clang++ -O2 -m64 -march=native -std=c++11 main.cpp && ./a.out
N: comparisons
100: 1742
200: 4260
400: 10035
800: 22784
1600: 51049
3200: 112386
6400: 244850

Inspecting the source of <algorithm> shows the cause of the issue: there is no
introsort implemented, only quicksort (albeit with non-trivial optimizations,
but nothing preventing the worst case). I've written a patch that augments the
current implementation to make it work as an introspective sort, switching to
heapsort if the recursion depth exceeds 2*floor(log(N)). This post can only
have one attachment, so I'll post it as an attachment to a comment.

Having not contributed to libc++ before I'm not 100% familiar with all coding
styles/(un)written rules. My changes are rather minimal though, so I've just
followed what style could be found in context. And of course I knowingly submit
my code under the libc++ licenses, the MIT license and the UIUC License.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20140902/cb4c5141/attachment.html>