java中集合#排序方法的时间复杂度是多少？[英] What is the time complexity of Collections#sort method in Java?

问题描述

What is the time complexity of Collections#sort method in Java? Which algorithm is used?

Is Collection#sort a good method for sorting an ArrayList of 10^6?

推荐答案

This depends on the version of Java you use. But in the end, the Big-O time complexity is still O(N*log(N)).

For Java 6, it's a modified version of mergesort. Check the description here: Collections#sort for Java 6

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). This algorithm offers guaranteed n log(n) performance. The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

For Java 7, it was improved: Collections#sort for Java 7 due to enhancement. Note that TimSort has a best case of O(N) and proves to be faster than the previous implementation.

Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.

The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techiques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

Is this a good method for sorting an ArrayList of 10^6?

In theory, it is enough to use. But this makes me wonder why would you have to sort the data in memory. If the data comes from a database, then sort it there using an indexed column/field, otherwise check if you know some characteristics of the field you will use for sorting and if you may use a O(N) time complexity algorithm like Bucket Sort or Radix Sort. When there's no other way, use Collections#sort.

其他推荐答案

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().

Information present in collections documentation -

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). This algorithm offers guaranteed n log(n) performance.