Java Performance Tuning, 2nd Edition

Chapter 9. Sorting

Avoiding Unnecessary Sorting Overhead

The JDK system provides sorting methods in java.util.Arrays (for arrays of objects) and in java.util.Collections (for objects implementing the Collection interfaces). These sorts are usually adequate for all but the most specialized applications. To optimize a sort, you can normally get enough improvement by reimplementing a standard sort (such as quicksort) as a method in the class being sorted. Comparisons of elements can then be made directly, without calling generic comparison methods. Only the most specialized applications usually need to search for specialized sorting algorithms.

As an example, here is a simple class with just an int instance variable, on which you need to sort:

public class Sortable
  implements Comparable
{
  int order;
  public Sortable(int i){order = i;}
  public int compareTo(Object o){return order - ((Sortable) o).order;}
  public int compareToSortable(Sortable o){return order - o.order;}
}

I can use the Arrays.sort( ) to sort this, but as I want to make a direct comparison with exactly the same sorting algorithm as I tune, I use an implementation of a standard quicksort. (This implementation is not shown here; for an example, see the quicksort implementation in Section 11.9.) The only modification to the standard quicksort will be that for each optimization, the quicksort is adjusted to use the appropriate comparison method and data type. For example, a generic quicksort that sorts an array of Comparable ...