java - Is it faster to add to a collection then sort it, or add to a sorted collection?

Question

If I have a Map like this:

HashMap<Integer, ComparableObject> map;

and I want to obtain a collection of values sorted using natural ordering, which method is fastest?

(A)

Create an instance of a sortable collection like ArrayList, add the values, then sort it:

List<ComparableObject> sortedCollection = new ArrayList<ComparableObject>(map.values());
Collections.sort(sortedCollection);

(B)

Create an instance of an ordered collection like TreeSet, then add the values:

Set<ComparableObject> sortedCollection = new TreeSet<ComparableObject>(map.values());

Note that the resulting collection is never modified, so the sorting only needs to take place once.

Answer 1

TreeSet has a log(n) time complexity guarantuee for add()/remove()/contains() methods. Sorting an ArrayList takes n*log(n) operations, but add()/get() takes only 1 operation.

So if you're mainly retrieving, and don't sort often, ArrayList is the better choice. If you sort often but dont retrieve that much TreeSet would be a better choice.