Why does a Java sorting implementation convert a list to an array before sorting?

Question

In JDK 1.8, the first instruction of the java.util.List#sort(Comparator) method is as follows:

 Object[] a = this.toArray(); 

It is worth copying the list into an array, sorting it and reset each node of the list into a sorted value from the array.

It seems that when sorting an ArrayList it is not possible to copy the values ​​into a temporary array. I'm right? If not, what were the creators of the method guided by?

Answer 1

sort in the java.util.List interface is just the default implementation of list sorting.

ArrayList overrides this default value with a sort method that directly sorts its internal array.

Answer 2

For ArrayList or other random access lists, you may be right.

However, Collections.sort supports any List implementation. For example, it would be very convenient for LinkedList to change elements during sorting (since finding the ith element takes linear time).

Converting the list to an array and setting the elements of the original list after sorting the array adds a linear time component to the algorithm, which does not change the asymptotic time of operation (O(nlog(n))) .

Answer 3

In OpenJDK 1.8, java.util.ArrayList#sort(Comparator) does not copy its internal array; it is sorted locally, as you think it should.

The java.util.List#sort() implementation that you criticize contains the following accompanying documentation:

The default implementation gets an array containing all the elements in this list, sorts the array and iterates over this list, discarding each element from the corresponding position in the array. (This avoids the n² log (n) performance that would occur when trying to sort a linked list in place.)

That is, copying an array and moving with random access is more efficient than the overhead of linear moving in a linked list. A regular implementation tries to exchange the overhead for the transfer of the overhead of the element. For cases like ArrayList , where copying is not required to get the same random access to elements, the library skips the copy by overriding the method.

An interesting comparison: look at the functions of the standard C ++ library std::sort() and std::list::sort() :

• std::sort() Requires parameters that limit a range with random access.
• std::list::sort() Only linear access is assumed by moving the nodes of the linked list.

The general std::sort() algorithm is more efficient, but the library does not allow calling it on std::list (which is a linked list, similar to Java java.util.LinkedList ). The library provides less efficient means for sorting std::list for convenience. Unlike the Java library, the C ++ library does not copy std::list() into an array to use the random access algorithm std::sort() .