Hi,

I have a question related to the sort function.
Does anyone know which algorithm is used in the built-in array sort function.
I needed to sort 256 integers. By using a radix sort, i got 30 usec on my laptop. But using the built-in sort, i get 20 usec.
I thought the radix sort was pretty efficient.
Any idea?

Alain

Alain wrote:
> Hi,
> 
> I have a question related to the sort function.
> Does anyone know which algorithm is used in the built-in array sort function.
> I needed to sort 256 integers. By using a radix sort, i got 30 usec on my laptop. But using the built-in sort, i get 20 usec.
> I thought the radix sort was pretty efficient.
> Any idea?

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.

/Oskar

Alain wrote:
> Hi,
> 
> I have a question related to the sort function.
> Does anyone know which algorithm is used in the built-in array sort function.
> I needed to sort 256 integers. By using a radix sort, i got 30 usec on my laptop. But using the built-in sort, i get 20 usec.
> I thought the radix sort was pretty efficient.
> Any idea?

Radix sort's running time has a larger multiplier than qsort. Try sorting more numbers and beyond a side radix sort may win.

Andrei

Andrei Alexandrescu (See Website For Email) Wrote:

> Alain wrote:
> > Hi,
> > 
> > I have a question related to the sort function.
> > Does anyone know which algorithm is used in the built-in array sort function.
> > I needed to sort 256 integers. By using a radix sort, i got 30 usec on my laptop. But using the built-in sort, i get 20 usec.
> > I thought the radix sort was pretty efficient.
> > Any idea?
> 
> Radix sort's running time has a larger multiplier than qsort. Try sorting more numbers and beyond a side radix sort may win.
> 
> Andrei

You may also want to try shell sort, it's very efficient and easy to implement. Radix Sort takes a very large block of data to be the fastest algorithm. I compared it against shell sort before, it took a few million elements for radix sort to be quicker.

Xinok wrote:
> Andrei Alexandrescu (See Website For Email) Wrote:
> 
>> Alain wrote:
>>> Hi,
>>> 
>>> I have a question related to the sort function. Does anyone know
>>> which algorithm is used in the built-in array sort function. I
>>> needed to sort 256 integers. By using a radix sort, i got 30 usec
>>> on my laptop. But using the built-in sort, i get 20 usec. I
>>> thought the radix sort was pretty efficient. Any idea?
>> Radix sort's running time has a larger multiplier than qsort. Try sorting more numbers and beyond a side radix sort may win.
>> 
>> Andrei
> 
> You may also want to try shell sort, it's very efficient and easy to
> implement. Radix Sort takes a very large block of data to be the
> fastest algorithm. I compared it against shell sort before, it took a
> few million elements for radix sort to be quicker.

Shell sort? I thought it sucks. :o) Why would anyone use it?

Andrei

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