Why isn't Collections.sort() optimized for ArrayList, but is for LinkedList?

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

edited Jan 13 at 10:49

Slaw

7,90331033

asked Jan 13 at 10:41

Vineeth Chitteti

713522

Please PM here if the question is a possible duplicate. I will be glad to know that there is already an answer to this question.

– Vineeth Chitteti
Jan 13 at 10:42

add a comment |

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

edited Jan 13 at 10:49

Slaw

7,90331033

asked Jan 13 at 10:41

Vineeth Chitteti

713522

Please PM here if the question is a possible duplicate. I will be glad to know that there is already an answer to this question.

– Vineeth Chitteti
Jan 13 at 10:42

add a comment |

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

edited Jan 13 at 10:49

Slaw

7,90331033

asked Jan 13 at 10:41

Vineeth Chitteti

713522

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

java algorithm sorting timsort

edited Jan 13 at 10:49

Slaw

7,90331033

asked Jan 13 at 10:41

Vineeth Chitteti

713522

edited Jan 13 at 10:49

Slaw

7,90331033

asked Jan 13 at 10:41

Vineeth Chitteti

713522

edited Jan 13 at 10:49

Slaw

7,90331033

edited Jan 13 at 10:49

Slaw

7,90331033

edited Jan 13 at 10:49

Slaw

7,90331033

asked Jan 13 at 10:41

Vineeth Chitteti

713522

asked Jan 13 at 10:41

Vineeth Chitteti

713522

asked Jan 13 at 10:41

Vineeth Chitteti

713522

Please PM here if the question is a possible duplicate. I will be glad to know that there is already an answer to this question.

– Vineeth Chitteti
Jan 13 at 10:42

add a comment |

Please PM here if the question is a possible duplicate. I will be glad to know that there is already an answer to this question.

– Vineeth Chitteti
Jan 13 at 10:42

Please PM here if the question is a possible duplicate. I will be glad to know that there is already an answer to this question.

– Vineeth Chitteti
Jan 13 at 10:42

add a comment |

1 Answer
1

active

oldest

votes

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

edited Jan 13 at 11:14

answered Jan 13 at 10:44

Eran

284k37460547

1

The link to the source file (supposedly for JDK8, though I don't fully understand the repo's organization) does show Collections.sort using the default List.sort implementation directly.

– Slaw
Jan 13 at 10:48

Not what I see; I see sorting done on the toArray() on line 230 (perhaps you're looking at the synchronized wrapper?). That said, OpenJDK11 is showing what you're saying in its source.

– Joe C
Jan 13 at 10:56

1

@Slaw the linked source file seems to be jdk8-b132. My answer contains code of JDK 1.8.0_162

– Eran
Jan 13 at 10:57

Here's the JDK9 version - hg.openjdk.java.net/jdk9/jdk9/jdk/file/d966fc5a7be5/src/…. I'll link to JDK 1.8.0_162 if I can find it

– Eran
Jan 13 at 11:00

@Eran hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/c00bdbbd9a77/src/share/…

– eckes
Jan 13 at 11:09

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54168052%2fwhy-isnt-collections-sort-optimized-for-arraylist-but-is-for-linkedlist%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

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

edited Jan 13 at 11:14

answered Jan 13 at 10:44

Eran

284k37460547

1

The link to the source file (supposedly for JDK8, though I don't fully understand the repo's organization) does show Collections.sort using the default List.sort implementation directly.

– Slaw
Jan 13 at 10:48

Not what I see; I see sorting done on the toArray() on line 230 (perhaps you're looking at the synchronized wrapper?). That said, OpenJDK11 is showing what you're saying in its source.

– Joe C
Jan 13 at 10:56

1

@Slaw the linked source file seems to be jdk8-b132. My answer contains code of JDK 1.8.0_162

– Eran
Jan 13 at 10:57

Here's the JDK9 version - hg.openjdk.java.net/jdk9/jdk9/jdk/file/d966fc5a7be5/src/…. I'll link to JDK 1.8.0_162 if I can find it

– Eran
Jan 13 at 11:00

@Eran hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/c00bdbbd9a77/src/share/…

– eckes
Jan 13 at 11:09

add a comment |

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

edited Jan 13 at 11:14

answered Jan 13 at 10:44

Eran

284k37460547

1

The link to the source file (supposedly for JDK8, though I don't fully understand the repo's organization) does show Collections.sort using the default List.sort implementation directly.

– Slaw
Jan 13 at 10:48

Not what I see; I see sorting done on the toArray() on line 230 (perhaps you're looking at the synchronized wrapper?). That said, OpenJDK11 is showing what you're saying in its source.

– Joe C
Jan 13 at 10:56

1

@Slaw the linked source file seems to be jdk8-b132. My answer contains code of JDK 1.8.0_162

– Eran
Jan 13 at 10:57

Here's the JDK9 version - hg.openjdk.java.net/jdk9/jdk9/jdk/file/d966fc5a7be5/src/…. I'll link to JDK 1.8.0_162 if I can find it

– Eran
Jan 13 at 11:00

@Eran hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/c00bdbbd9a77/src/share/…

– eckes
Jan 13 at 11:09

add a comment |

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

edited Jan 13 at 11:14

answered Jan 13 at 10:44

Eran

284k37460547

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

edited Jan 13 at 11:14

answered Jan 13 at 10:44

Eran

284k37460547

edited Jan 13 at 11:14

answered Jan 13 at 10:44

Eran

284k37460547

answered Jan 13 at 10:44

Eran

284k37460547

answered Jan 13 at 10:44

Eran

284k37460547

1

The link to the source file (supposedly for JDK8, though I don't fully understand the repo's organization) does show Collections.sort using the default List.sort implementation directly.

– Slaw
Jan 13 at 10:48

Not what I see; I see sorting done on the toArray() on line 230 (perhaps you're looking at the synchronized wrapper?). That said, OpenJDK11 is showing what you're saying in its source.

– Joe C
Jan 13 at 10:56

1

@Slaw the linked source file seems to be jdk8-b132. My answer contains code of JDK 1.8.0_162

– Eran
Jan 13 at 10:57

Here's the JDK9 version - hg.openjdk.java.net/jdk9/jdk9/jdk/file/d966fc5a7be5/src/…. I'll link to JDK 1.8.0_162 if I can find it

– Eran
Jan 13 at 11:00

@Eran hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/c00bdbbd9a77/src/share/…

– eckes
Jan 13 at 11:09

add a comment |

1

The link to the source file (supposedly for JDK8, though I don't fully understand the repo's organization) does show Collections.sort using the default List.sort implementation directly.

– Slaw
Jan 13 at 10:48

Not what I see; I see sorting done on the toArray() on line 230 (perhaps you're looking at the synchronized wrapper?). That said, OpenJDK11 is showing what you're saying in its source.

– Joe C
Jan 13 at 10:56

1

@Slaw the linked source file seems to be jdk8-b132. My answer contains code of JDK 1.8.0_162

– Eran
Jan 13 at 10:57

Here's the JDK9 version - hg.openjdk.java.net/jdk9/jdk9/jdk/file/d966fc5a7be5/src/…. I'll link to JDK 1.8.0_162 if I can find it

– Eran
Jan 13 at 11:00

@Eran hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/c00bdbbd9a77/src/share/…

– eckes
Jan 13 at 11:09

The link to the source file (supposedly for JDK8, though I don't fully understand the repo's organization) does show Collections.sort using the default List.sort implementation directly.

– Slaw
Jan 13 at 10:48

Not what I see; I see sorting done on the toArray() on line 230 (perhaps you're looking at the synchronized wrapper?). That said, OpenJDK11 is showing what you're saying in its source.

– Joe C
Jan 13 at 10:56

@Slaw the linked source file seems to be jdk8-b132. My answer contains code of JDK 1.8.0_162

– Eran
Jan 13 at 10:57

Here's the JDK9 version - hg.openjdk.java.net/jdk9/jdk9/jdk/file/d966fc5a7be5/src/…. I'll link to JDK 1.8.0_162 if I can find it

– Eran
Jan 13 at 11:00

@Eran hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/c00bdbbd9a77/src/share/…

– eckes
Jan 13 at 11:09

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Jtdylktuy