CODEWITHSUNDEEP
javaperformancesorting
ashes999
ashes999

Reputation: 10163

Collections.Sort performance on subsequent sorts?

I'm using Collections.sort with a custom comparator class. I've heard that this has O(N log N) runtime complexity. I'm curious to know what happens on subsequent sorts when the collection hasn't changed.

By example, lets say I have an ArrayList of Eggs, each which has an approximate size field (which my comparator sorts by). If I insert ten eggs into the array list, and sort it, I can expect it to take O(N log N) time.

If I sort it again, without adding, removing, or changing any elements, will it still take N log N time?

Upvotes: 2

Views: 972

Answers (4)

allingeek
allingeek

Reputation: 1388

To expand on EJP's answer, if the documentation indicates that the merge pass is the step skipped, then in this best case runtime would be LG N because it will still break the list into LG N subproblems. The multiplication against the linear scan is the improvement in efficiency.

Upvotes: 0

user207421
user207421

Reputation: 310859

The Javadoc says 'the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist'. That appears to mean nothing happens so it should be quicker.

You could always test it.

Upvotes: 2

Alexander Pogrebnyak
Alexander Pogrebnyak

Reputation: 45576

Per JavaDoc Collections.sort uses merge sort algorithm.

You can see how it does, for yourself, here -> http://www.sorting-algorithms.com/

Upvotes: 0

E-K
E-K

Reputation: 1491

I have not analysed the code in the current sun java library. However, the javadoc states that a merge sort is used. Most merge sorts yield a O(n) performance on already sorted collection. Although this is not stated in the documentation. My personal experience has shown me really good performance on sorted or nearly sorted lists.

Upvotes: 1

Related Questions