Aioobe's approach is the way to go. I would like to suggest the following improvement over his solution though.
class SortedList<T> extends ArrayList<T> {
public void insertSorted(T value) {
int insertPoint = insertPoint(value);
add(insertPoint, value);
}
/**
* @return The insert point for a new value. If the value is found the insert point can be any
* of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
*/
private int insertPoint(T key) {
int low = 0;
int high = size() - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = (Comparable<T>) get(mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else {
return mid; // key found
}
}
return low; // key not found
}
}
aioobe's solution gets very slow when using large lists. Using the fact that the list is sorted allows us to find the insert point for new values using binary search.
I would also use composition over inheritance, something along the lines of
SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable