## digitalmars.D - Sort algorithm

- 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?

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

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

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

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

Andrei Alexandrescu (See Website For Email) Wrote:Alain wrote: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.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 wrote:Andrei Alexandrescu (See Website For Email) Wrote:Shell sort? I thought it sucks. :o) Why would anyone use it? AndreiAlain wrote: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