Implementing an Insertion Sort in Java

The code below shows an example insertion sort implementation in Java. As discussed in our section on the performance of Java's sort algorithm, for very small lists, it can be faster to use a simple algorithm such as this. Although the insertion sort doesn't scale well, it doesn't have the overhead of making a copy of the list, doesn't need to create any new objects during sorting, and avoids recursive calls (leaving the non-recursive calls to compareTo() and get()/set() which can be inlined by modern VMs).

  public static <T extends Comparable<T>> void insertionSort(List<T> l) {
    for (int sz=l.size(), i=1; i<sz; i++) {
      int j = i;
      while (j > 0) {
        T prev = l.get(j-1);
        T thisOne = l.get(j);
        if (prev.compareTo(thisOne) > 0) {
          l.set(j-1, thisOne);
          l.set(j, prev);
        } else {
          break;
        }
        j--;
      }
    }
  }