Insertion Sort in Java

Sorting means arranging data in a defined order, such as ascending numbers or alphabetical names, so that it can be searched, merged and displayed easily. Each sorting algorithm makes different trade-offs between speed, memory and stability.

This tutorial covers insertion sort, the way most people sort a hand of playing cards: pick up one card at a time and slide it into its correct place among the cards already in your hand.

How Insertion Sort Works

Insertion sort keeps a sorted prefix at the start of the array. Initially it contains just the first element. In each step it takes the next element, shifts every larger value in the prefix one position to the right, and puts the element into the gap that opens up.

1. Start with i = 1; the prefix array[0..0] is trivially sorted.
2. Save value = array[i].
3. Walk left from i − 1, shifting each element greater than value one place to the right.
4. Write value into the position just after the last element that is not greater than it.
5. Increase i and repeat until the end of the array.

Dry run for [7, 3, 9, 2] (the sorted prefix is shown before the bar):

start:            [7 | 3, 9, 2]
insert 3:         [3, 7 | 9, 2]      (7 shifted right)
insert 9:         [3, 7, 9 | 2]      (no shift needed)
insert 2:         [2, 3, 7, 9]       (9, 7 and 3 shifted right)

Java program for implementation of Insertion Sort

// Insertion sort: grow a sorted prefix by inserting one new value at a time
public class InsertionSortExample {

  static void insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
      int value = array[i];            // next value to place
      int j = i - 1;
      // shift larger values in the sorted prefix one step to the right
      while (j >= 0 && array[j] > value) {
        array[j + 1] = array[j];
        j--;
      }
      array[j + 1] = value;            // drop the value into the gap
    }
  }

  static void printArray(int[] array) {
    StringBuilder line = new StringBuilder();
    for (int value : array) {
      line.append(value).append(' ');
    }
    System.out.println(line.toString().trim());
  }

  public static void main(String[] args) {
    int[] array = {40, 70, 90, 20, 80, 100, 60, 10, 30, 50};
    System.out.println("Created array elements:");
    printArray(array);

    insertionSort(array);

    System.out.println();
    System.out.println("Sorted array elements:");
    printArray(array);
  }
}

Created array elements:
40 70 90 20 80 100 60 10 30 50

Sorted array elements:
10 20 30 40 50 60 70 80 90 100

Time and Space Complexity

Space: O(1) extra; insertion sort sorts in place. It is stable (the loop stops at an equal value, so equal elements keep their order) and online (it can sort values as they arrive).

When to Use Insertion Sort

• Small arrays: its tiny overhead makes it faster than O(n log n) algorithms for a few dozen elements, which is why library sorts such as Java's switch to insertion sort for small sub-arrays.
• Nearly sorted data: the running time is O(n + k), where k is the number of out-of-order pairs, so almost-sorted input is handled in close to linear time.
• Not for large random data: there its O(n²) running time is far slower than merge sort, quick sort or Arrays.sort().