I was talking with one of my co-workers the other day about things that we had learned in our classes at our respective universities. I started thinking back to the classes I took at my alma mater for Data Structures and Software Engineering. I remember always being intrigued by the different sorting algorithms. On a separate note, I had read some rumors a while back that Java was replacing all sorting with Timsort as of Java 7. After taking a look at the API docs, however, I am glad to see that Quicksort is still being used. I always liked Quicksort’s simple elegance and it is a good overall sorting algorithm for medium to large-sized lists.

I am not going to go into the theory behind Quicksort or talk about any Big-O notation stuff here, as that is found anywhere on the web. I am also not saying that this is the most efficient implementation of this algorithm because I know that it isn’t. One thing that would make this sort run faster is to switch to a different algorithm such as Insertion sort when the size of a sub list during a recursive call falls below a certain threshold, as Quicksort does not do well on smaller lists. In my tests, this algorithm was sorting an array of 10,000,000 random Integer objects consistently in just over 8 seconds.

The source code is available here.