Home  Collections intro  Lists  Maps  Sets  Which collection class?  Sorting  Hashing  Advanced
 Video lecture: hash tables  Bloom filters

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--;
      }
    }
  }
comments powered by Disqus

Written by Neil Coffey. Copyright © Javamex UK 2012. All rights reserved. If you have any feedback on the Java collections tutorials in this section or about the content of this site in general, please leave a message on the Javamex forum.