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

Question

In JDK 1.8, the first statement of the java.util.List#sort(Comparator) method is the following:

Object[] a = this.toArray();

It's expensive to copy the list into an array, sort it, and reset every node of the list to the sorted value from the array.

It seems like it's possible not to copy values to a temporary array when sorting an ArrayList. Am I right? If not, what guided the creators of the method?

Answer 1

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

ArrayList overrides this default with a sort method which does sort its internal array directly.

Answer 2

For ArrayList, or other random access Lists, you may be correct.

However, Collections.sort supports any List implementation. For a LinkedList, for example, it would have been very expansive to swap elements during the sort (since finding the i'th element takes linear time).

Converting the List to an array, and setting the elements of the original List after the array is sorted adds a linear time component to the algorithm, which doesn't change the asymptotic running time of (O(nlog(n))).