Why is Collections.sort() optimised for LinkedList, but is not optimised for ArrayList?

user_2381544 0
Viewed 378

Why does Collections.sort() creates an extra object array and performs Tim sort on the array and then finally copies the sorted array back into List object? I know this call is optimized for LinkedList, but won't we lose out on performance for ArrayList?

We could have avoided 2n number of operations in converting it into an object array and adding them back to the list. I know that these extra operations wouldn't affect the Big-O of the whole sorting operation, but I believe it could've been further optimised for ArrayList.

Am I missing something here? I'm just trying to understand why the architecture is laid out as such. Thanks.

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

timsort sorting algorithm java
1 Answers

You are looking at an older JDK version. At least since since JDK 1.8.0_162 Collections.sort() calls List's sort(Comparator<? super E> c). And while the default implementation creates an array from the List and sorts that array, ArrayList overrides that default implementation, and sorts the backing array directly.

Collections's sort:

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

List's 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's 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++;
}

In other words, this has been addressed in JDK versions newer than the one you are looking at.

You can look at the source here (thanks to eckes's link).

user_12215710
Related