## digitalmars.D - Sort algorithm

Alain <alainpoint yahoo.fr> writes:
```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
```
Jan 24 2007
Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
```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
```
Jan 24 2007
Joe Gottman <jgottman carolina.rr.com> writes:
```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
```
Jan 24 2007
"Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
```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
```
Jan 24 2007
Xinok <xnknet gmail.com> writes:
```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.
```
Jan 24 2007
"Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
```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
```
Jan 24 2007