File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Algorithm Used for java.util.Collections Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Algorithm Used for java.util.Collections" Watch "Algorithm Used for java.util.Collections" New topic
Author

Algorithm Used for java.util.Collections

Prakash Rai
Ranch Hand

Joined: Jan 10, 2011
Posts: 101

Q. On which sorting Algorithm Collections.sort() and Arrays.sort() has been implemented ? I have gone through the java specification but I did't understand. Thanks in Advance.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 13868
    
  10

The Java specification does not say which sort algorithm is used. Did you read the API documentation of java.util.Collections.sort()? It explains exactly what implementation is used:
API documentation wrote:
Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.

The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techiques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

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. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Algorithm Used for java.util.Collections
 
Similar Threads
max contrast algorithim
DES algorithm sorce code
Needs help for grouping data
Java Questions in Interview
WA #1.....word association