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--;
      }
    }
  }

If you enjoy this Java programming article, please share with friends and colleagues. Follow the author on Twitter for the latest news and rants.

Editorial page content written by Neil Coffey. Copyright © Javamex UK 2021. All rights reserved.