D graph library -- update

[Andrei Alexandrescu]

On 7/11/13 3:25 AM, Joseph Rushton Wakeling wrote:
> By default, schwartzSort uses SwapStrategy.unstable, which means quicksort is
> used as the sorting mechanism.  If we replace this with SwapStrategy.stable or
> SwapStrategy.semistable, TimSort is used instead, and this dramatically cuts the
> running time -- from almost 2 minutes to under 3 seconds (compared to 13 seconds
> for igraph with one-by-one edge addition), and under 2 if ldmd2 is used for
> compiling.

Unstable sort should be faster than stable sort. If I remember correctly 
(1) our TimSort is indeed slower than quicksort on random numbers, (2) 
there is a performance bug that makes our quicksort perform 
quadratically on data that's essentially sorted but has one unsorted 
element at the end. Is that the case?

Andrei