I had not intended to post about the Java sort again but after working on a project today where I had to create a Comparator within my class I decided I would add this to the madness.   The problem is, my sort was messed up so the bug must have been in my compareTo() method.  Some background, I have a class that implements Comparator<TreeEntry> and in the compareTo() method I simply compare the labels in a tree to sort them alphabetically.  Btw, I love generics in Java!

Well, when I was debugging my compareTo() method I noticed the call stack and I thought, hhm, this would be some good information to share since I just wrote about sorting arrays!

Hitting my break point in the debugger I quickly noticed the “Arrays.mergeSort()” calls in the stack.

Check out the stack:

Arrays.sort() Java Callstack

So this is interesting!  It looks like Java, under the covers, uses some variation of the Merge sort algorithm.  Now, once again, I have not looked at the Java code but looking at the signature of the “merge” method it is identical to the classic Merge sort I referenced in the original post.