Menu
I'm using Collections.sort() to sort a LinkedList whose elements implements Comparable interface, so they are sorted in a natural order. In the javadoc documentation its said this method uses mergesort algorithm which has n*log(n) performance.
My question is if there is a more efficient algorithm to sort my LinkedList?
The size of that list could be very high and sort will be also very frequent.
363
So YES it's very fast (even in the worst case), much faster than a O(n^2) sorting algorithm.
The time complexity of Collections. sort() is O(n*log(n)) and a list sorted with Collections. sort() will only be sorted after the call to sort(). The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist).
The best general purpose or 'primary' implementations are likely ArrayList , LinkedHashMap , and LinkedHashSet . Their overall performance is better, and you should use them unless you need a special feature provided by another implementation. That special feature is usually ordering or sorting.
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort. The specified list must be modifiable, but need not be resizable.
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.
99
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
