Java - Collections.sort() performance
If you say the list will be sorted "very frequent", you should consider holding the list in a sorted stated all the time, like using a tree instead of a LinkedList. Maybe you can even use some SortedSet instead of a List, if you don't have any duplicated values and don't need any List operations (as you are sorting them anyway all the time). Check the TreeSet class of the SortedSet implementation.
This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
If you want to iterate over this "list" (which is actually a Set) you can use the Iterator of the class.
Returns an iterator over the elements in this set in ascending order.
If you have duplicate values inside the List you have to use some tricks (like putting the value in a new class which also got some delta for sorting equal object)
O(N log N) is very good asymptotically. That said, there are linear time O(N) non-comparison based sort, e.g. counting sort and bucket sort. This is useful when, e.g. you're sorting millions and millions of integers, but they're between 1..10.
Also, if the list is "almost sorted", the otherwise quadratic insertion sort is reported to actually be better under some scenarios.
Whether or not this is applicable, or even worth to implement, depends on your profiling results. I'd say that unless it shows the sort to be a bottleneck, don't worry about it.
See also
- Wikipedia/Counting sort
- Wikipedia/Bucket sort
Related questions
- Is there an O(n) integer sorting algorithm?