On 12/4/2011 4:42 AM, Martin Gregorie wrote:
On Sat, 03 Dec 2011 20:05:24 -0800, Roedy Green wrote:
On Sat, 03 Dec 2011 07:44:48 -0500, Eric Sosman
<esosman@ieee-dot-org.invalid> wrote, quoted or indirectly quoted
someone who said :
What is the big-Oh complexity of Collections.sort(List<String>)
on an already-sorted list?
IIRC QuickSort goes a bit bananas if the file is already sorted. ISTR
some sort doing some random swaps at the start to make sure that does
not happen. It does do a check first if things are in order.
I'm a little wary of quicksort's claim of superior speed in every
situation.
I would be a lot wary of that claim if I ever saw it made. As pointed
out at the start of its Wikiedia article, it "on average, makes O(nlog
n) (big O notation) comparisons to sort n items. In the worst case, it
makes O(n2) comparisons, though this behavior is rare. Quicksort is
often faster in practice than other O(nlog n) algorithms"
The key words here are "on average" and "often faster". To test those
claims, it would be necessary to do many runs, in many different
situations, with different inputs.
However, I think the java.util developers made the right call in
deciding not to use it. Given that there are very effective algorithms
that are truly O(n log(n)), not just on average, why not use one of them?
Patricia
Sort. Not sure why anyone would want to do that in a real life