• Alain (7/7) Jan 24 2007 Hi,
• Oskar Linde (8/15) Jan 24 2007 The built in sort uses quick sort, falling back on insertion sort when
• Joe Gottman (7/13) Jan 24 2007 You might want to try introsort (see
• Andrei Alexandrescu (See Website For Email) (4/11) Jan 24 2007 Radix sort's running time has a larger multiplier than qsort. Try
• Xinok (2/15) Jan 24 2007 You may also want to try shell sort, it's very efficient and easy to imp...
• Andrei Alexandrescu (See Website For Email) (3/22) Jan 24 2007 Shell sort? I thought it sucks. :o) Why would anyone use it?

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

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

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

"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

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.

"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