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
