为什么Collections.sort()针对LinkedList进行了优化，但没有针对ArrayList进行优化？

Question

为什么Collections.sort()要创建一个额外的对象数组，并对该数组执行Tim排序，最后将排序后的数组复制回List对象？我知道这个调用针对LinkedList进行了优化，但是我们不会损失ArrayList的性能吗

在将其转换为对象数组并将其添加回列表时，我们本可以避免2n数量的操作。我知道这些额外的操作不会影响整个排序操作的大O，但我相信它可以针对ArrayList进一步优化。

我是不是漏掉了什么？我只是想弄明白为什么架构是这样布局的。谢谢。

https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/Collections.java#l164

Answer 1

您看到的是一个较旧的JDK版本。至少自从JDK 1.8.0_162 Collections.sort()调用List的sort(Comparator<? super E> c)以来，虽然默认实现从List创建数组并对该数组进行排序，但ArrayList覆盖了该默认实现，并直接对后备数组进行排序。

Collections的sort

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

List的sort

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

ArrayList的sort

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

换句话说，这个问题已经在比您现在看到的版本更新的JDK版本中得到了解决。

您可以查看源代码here (感谢eckes的链接)。