www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Sort algorithm

reply 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
next sibling parent reply 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
parent 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
prev sibling parent reply "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
parent reply 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
parent "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?

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