Sorting and OpenJDK
By vaibhavc on Nov 25, 2009
If you are looking for sorting algorithms and if you use some sorting algorithm in your code/application/big application, then have a look here. First of all sorting/searching is a classic thing. It take more than 70 percent of your application time.People/Developer/Mathematician do a lot of work on optimizing this work to get Best, best out of best.
Early days, JDK used to use QuickSort which is one of the best sorting algorithm and go for a complexity of O(nlogn). But mind it, QuickSort is a recursive algorithm and consume space. Whereas some of the algorithm which has the complexity like O(n\^2) go for less complex in terms of memory. These days our platform varies from small mobile device to a terabyte storage machine.
JDK has improved sorting algorithm a lot, but the new one which is the sorting algorithm used in Android are get into OpenJDK. Have a look here: http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/jdk7-b76/src/share/classes/java/util/TimSort.java.
Code is awesomely understandable but just a small explaination. It start with merge sort, which has effecient complexity of O(nlogn). But when the nodes go too much it merge, it calls binary insertion sorting, which is one of the best for small number of elements. Read this comment :
\* Sorts the specified portion of the specified array using a binary
\* insertion sort. This is the best method for sorting small numbers
\* of elements. It requires O(n log n) compares, but O(n\^2) data
\* movement (worst case).
I don't know is there any document available who did the actually benchmarking but if I get time, I would love to do checking with all worst/avg cases. It's a nice and tricky algorithm which take care of time complexity and space complexity both.