I had a discussion the other day about writing your own sorting code versus using the built in Java sort. So tonight I decided to do a little geek research for the fun of it. Now, I will say, I have rarely ever rolled my own sorting algorithm in Java (if ever). In C, yes, C++, maybe – until STL came around. So I decided to do a test. I scoured the internet (ok, a couple of Google searches) for a good sample of a Quick Sort(link here) and a Merge Sort(from here) and then I compared them to the built in Java sort (Arrays.sort). The two code samples came from Java Tips, great site, check it out.
I did see some interesting numbers when I changed the number of elements or the kind of elements I sorted. I ended up using a string concatenated with the current time in milliseconds to fill the array. I ended up running a series of tests where the sample ranged from 10,000 entries to 200,000 entries. Is this likely in the real world? Probably not, but it makes for some good geek discussion!
Code to fill the array:
private static void fillArray(List<String> array) {
Random generator2 = new Random( System.currentTimeMillis() );
for (int x = 0; x<50000; x++){
array.add("Value = " + generator2.nextInt());
}
}
The following is a series of results after running the code 10 times. The results are the time it took to make each sort call in milliseconds.
I think the key takeaway from this table is you can consistently see the Java (Arrays.sort) consistently faster across the different element counts.
I do not know this for sure, I could look into the Java source to verify but I think the Arrays.sort must be using some kind of Introsort algorithm where it recognizes the recursion depth and dynamically switches to a heap sort when the recursion depth gets too high. One issue that is not shown here, is the Quick Sort and Merge Sort actually run out of memory on sets that are over a million (in a basic configuration). So this recursion optimization is actually a really big deal with very large sets and in short the Arrays.sort should probably be used in most cases.
The reality is, most data has some kind of sort out of the box and is rarely this random. The key however, is to really understand the various things going on within your sort code and running a few tests like this may in the end save you a lot of programming time.
