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

user_402033 0
Viewed 35419

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.

collections sorting java
7 Answers

Inserting in a SortedSet is O(log(n)) (BUT! the current n and not the final n). Inserting in a List is 1.

Sorting in a SortedSet is already included in inserting, so it is 0. Sorting in a List is O(n*log(n)).

So SortedSet total complexity is O(n * k), k < log(n) for all cases but the last. Instead, List total complexity is O(n * log(n) + n), so O(n * log(n)).

So, SortedSet mathematically has the best performance. But in the end, you have a Set instead of a List (because SortedList doesn't exist) and Set provides you fewer features than List. So in my opinion, the best solution for available features and performance is the one proposed by Sean Patrick Floyd:

  • use a SortedSet for inserting,
  • put the SortedSet as a parameter for creating a List to return.
user_31282130

Great question and great answers. Just thought I would add some points to take into account:

  1. If your Collection to be sorted is short-lived, for instance, used as an argument to a method, and you need the list sorted within the method, then use Collections.sort(collection). Or if it is long-lived object, but you need to sort it very rarely.

Justification: The sorted collection is required for something specific, and you probably won't add or remove very often. So you don't really care about the elements in the collection once it is sorted. You basically:

sort -> use it -> forget

If you add a new element to the sorted collection, you will have to sort the collection again, as the order is not guaranteed when inserting a new element.

  1. If your Collection to be sorted is long-lived and/or if it is a field within a class and you need it to be sorted at all times then you should use a sorted data structure such as TreeSet.

Justification: You care about the collection order at all times. You want it to be sorted at all times. So if you constantly add or remove elements you have the guarantee that the collection is sorted. So basically:

insert/remove -> use it (all the time you have the guarantee that the collection is sorted)

There is no specific moment where you need the collection to be sorted, instead, you want the collection to be sorted all the time.

The downside of using TreeSet is the resources it requires to keep the sorted collection. It uses a Red-black tree, and it requires O(log n) time cost for get, put operations.

Whereas if you use a simple collection, such as an ArrayList, the get,add operations are O(1) constant time.

user_24381770
Related