To keep Markus' Wurm thread to its topic, I'll try move the "what algorithm is best to sort lists" sub-thread to this location. For a start I copy my last two articles.
Also I'd like to add that of course it always depends on one's task what has to be sorted in order to choose the right algorithm. So the topic's name isn't very accurate.
Radix sort is the way to go, it's an order of magnitude faster than Collections.sort() and ultimately it sorts in 5 log n speed instead of n log n which I believe Collections manages.
Radix sort ... sounds interesting. Thanks for the hint. I've read a little bit in an algorithm book... basically it says:
The heap sort (of the C++ STL for example) has a worst time O(n*log(n))
, with n being the number of elements in the list. It's not stable and the pre-sorting of the list doesn't help.
The Java "Collections.sort()" is a kind of merge sort, which has a worst time O(n*log(n))
. It is
stable however and it runs substantially faster on nearly sorted lists.
The radix sort has a O(n*s)
, with s being the size of the key. It is
stable and to pre-sorting of the list doesn't help.
Is that correct so far? Hope so. :-)
Well, it depends on whether you've got some kind of pre-sorting in the list, whether you need a stable sort, and how large the list (and the key size) is. :-) So I'll have to figure out which fits best to my alpha blending sorting.
Some other posters mentioned that memory consumption of a sort algorithm matters, too.
Still, I don't see why the Collection.sort() algorithm is slower than other good sorting algorithms, for example if you want to sort surfaces or particles which have got alpha transparency.
I always thought a O(n*log(n)) was pretty OK? Isn't it?