Tom Anderson wrote:
On Sun, 29 Mar 2009, Andreas Leitgeb wrote:
As it seems, sorting an ArrayList is a bit awkward, in that you have
to copy the contents to an array first, sort that, and then bring the
array back into an ArrayList, but I may have missed something there.
You may have missed this:
http://java.sun.com/javase/6/docs/api/java/util/Collections.html#sort(java.util.List,%20java.util.Comparator)
... which says, in part:
This implementation dumps the specified list into an array,
sorts the array, and iterates over the list resetting each
element from the corresponding position in the array.
That's pretty much the awkward operation Andreas described.
The Javadoc goes on to say:
This avoids the n^2 log(n) performance that would result from
attempting to sort a linked list in place.
... which is an admission of a drawback of the Holy Principles of
Encapsulation and Information Hiding. If the Collections class could
directly manipulate the links of a LinkedList, the sort could be done
in O(n lg(n)) time, in-place and without creating additional garbage.
The copy-sort-restore dance is not required by the inherent complexity
of the sorting problem, but by a limitation imposed by adherence to
OO purity.
java.util.RandomAccess. If it does, do the sort in-place. If not, dump