Sort algorithm

[Joe Gottman]

Oskar Linde wrote:

> The built in sort uses quick sort, falling back on insertion sort when 
> the slices get small enough. Which sorting algorithm is fastest depends 
> very much on the problem. How is your data distributed for instance? The 
> implementation is also very important. A template sorting function can 
> easily become 50 % faster than the D built in sort when operating on 
> primitive data types.
>

    You might want to try introsort (see 
http://www.cs.rpi.edu/~musser/gp/introsort.ps .) This is the same as 
quicksort, except that if the recursion depth gets too great it switches 
to heapsort.  It's almost as fast as quicksort in the general case and 
it is guaranteed to finish in O(N log N) time for all inputs.

Joe Gottman