Which Java sort is faster? Part 2

After taking some feedback and hearing further arguments I went ahead and automated a program that runs many permutations of the sort comparisons.  For these results I ran against an array that has 150,000 random strings that are sent into each different sort approach as I showed in the previous post.   I then wrapped these calls into a loop and ran that loop 50 times.  The results are a little different than the first set of tests but in the end the Java sort is much faster.  Maybe the next exercise would be to code a search that is as fast as the Java sort – without looking at the Java sort code…

Here are the average numbers.  Each set below is the average for a 150,000 element array running 50 times.  I actually ran this twice just to get another set of numbers.

Set 1

150,000 elements run 50 times
Average Merge Time = 176
Average Quick Time = 190
Average Java Time = 161

Set 2

150,000 elements run 50 times
Average Merge Time = 182
Average Quick Time = 200
Average Java Time = 165

6 thoughts on “Which Java sort is faster? Part 2

  1. I think this sort of misses the point. When comparing algorithms what you really care about is the asymptotic complexity. The only way to do the proper analysis is to know exactly what algorithm the “Java” sort is using.

    Quicksort can be worst case O(nlgn) or O(n^2) time depending on how the pivot is chosen. Using median-of-3 partitioning, I believe gets you O(nlgn). Mergesort is worst case O(nlgn) time but it uses O(n) space. Quicksort uses O(lgn) space.

    So with a good pivot, Quicksort is the champ.

  2. >> Wouldn’t you only know “the right pivot” if you knew about the data set?

    No. You just need to know how to choose the median of three different randomly chosen elements in the set. Your Quicksort implementation uses median-of-three partitioning. Finding the median is O(n) which might explain why your Quicksort shows slightly higher times in your tests. Assuming the “Javasort” uses some form of Mergesort, then the differences are probably just constant factors which is meaningless. Your tests do not prove which algorithm is more efficient.

    • I totally agree with the median partitioning but the entire point of this exercise was to take two search methods I found on Java-tips.org and use them against what ships in Java. Sort of making a point that the code you get off of the internet is not necessarily optimal. So in short, you are providing some good information to the post for how to make the sorts faster.

  3. Probably the most succinct plus informed data I stumbled upon for this subject. Indeed delighted that I stumbled upon the web site by chance. I’ll probably be opting-in to your own feed in order that I will receive the most recent updates. Like all the details here.

  4. Pingback: Java sorting – Part 3 » Balfes.net

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.