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

### Like this:

Like Loading...

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.

LikeLike

Wouldn’t you only know “the right pivot” if you knew about the data set? I am trying to prove general functions for sorting unknown data sets.

LikeLike

>> Wouldnt 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.

LikeLike

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.

LikeLike

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

LikeLike

Pingback: Java sorting – Part 3 » Balfes.net