Insertion Sort in Java

When you play cards and pick up one card at a time, you don't wait until you have all of them. You hold the cards already in your hand in order, and each new card slides into its correct place among them. Insertion sort works the same way: the left part of the array is always sorted, and each new element is inserted into it by shifting bigger elements one step to the right. It is the simple sort that real libraries actually use, for small and nearly sorted pieces of data. In this lesson, you will learn how insertion sort works, trace it, see why it is fast on nearly sorted input, and compare the three simple sorts.

What Is Insertion Sort?

Insertion sort in Java is a sorting algorithm that is used to build a sorted part one element at a time: it takes the next element from the unsorted part and shifts larger sorted elements right until it finds the gap where the new element belongs.

• It sorts in place with O(1) extra memory.
• It is stable.
• It is O(n²) in the worst case but O(n) on already sorted input, and very fast on nearly sorted input.
• It is online: it can sort elements as they arrive, one by one.

How It Works

1. Treat element 0 as a sorted part of size 1.
2. Take the next element as the key.
3. Compare the key with the elements of the sorted part, from right to left. Shift each larger one a step to the right.
4. Put the key into the gap that opens up.
5. Repeat until every element has been inserted.

Insertion Sort with a Trace

Let's see an example with the same five marks used in the previous two lessons.

import java.util.Arrays;
 
public class InsertionSort {
    static void insertionSort(int[] a) {
        for (int next = 1; next < a.length; next++) {
            int key = a[next];
            int j = next - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];          // shift the larger value right
                j--;
            }
            a[j + 1] = key;               // drop the key into the gap
            System.out.println("insert " + key + ": " + Arrays.toString(a));
        }
    }
 
    public static void main(String[] args) {
        int[] marks = {29, 10, 14, 37, 13};
        insertionSort(marks);
        System.out.println("sorted: " + Arrays.toString(marks));
    }
}

insert 10: [10, 29, 14, 37, 13]
insert 14: [10, 14, 29, 37, 13]
insert 37: [10, 14, 29, 37, 13]
insert 13: [10, 13, 14, 29, 37]
sorted: [10, 13, 14, 29, 37]

Explanation:

1. Insert 10: 29 is larger, so it shifts right, and 10 drops into index 0.
2. Insert 14: 29 shifts right; 10 isn't larger, so 14 goes between them.
3. Insert 37: nothing in the sorted part is larger, so no shifts happen and 37 stays where it is. This is why insertion sort is fast on sorted data.
4. Insert 13: 37, 29 and 14 all shift right, and 13 lands after 10.
5. The loop shifts values instead of swapping them, so each step does one write instead of three.

Fast on Nearly Sorted Data

Insertion sort does work only where elements are out of place. On an array that is almost sorted, most keys need no shifts at all.

public class NearlySorted {
    static int shifts(int[] a) {
        int count = 0;
        for (int next = 1; next < a.length; next++) {
            int key = a[next];
            int j = next - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
                count++;
            }
            a[j + 1] = key;
        }
        return count;
    }
 
    public static void main(String[] args) {
        int[] sorted = {1, 2, 3, 4, 5, 6, 7, 8};
        int[] nearly = {1, 2, 4, 3, 5, 6, 8, 7};
        int[] reversed = {8, 7, 6, 5, 4, 3, 2, 1};
        System.out.println("sorted:        " + shifts(sorted));
        System.out.println("nearly sorted: " + shifts(nearly));
        System.out.println("reversed:      " + shifts(reversed));
    }
}

sorted:        0
nearly sorted: 2
reversed:      28

Explanation: a sorted array needs no shifts, an array with two pairs of neighbors swapped needs only 2, and a reversed array needs the maximum, n(n - 1) / 2 = 28. The number of shifts equals the number of pairs that are out of order.

This is why the JDK uses insertion sort inside its fast sorts: when merge sort or quick sort has cut the data into small pieces, insertion sort finishes each small piece faster than recursing further.

Complexity

The Three Simple Sorts Compared

Common Mistakes

Losing the key. Shifting a[j] into a[j + 1] overwrites a[next]. Save it in key first.

Wrong loop condition order. a[j] > key && j >= 0 reads a[-1] when j reaches -1. Check j >= 0 first.

Putting the key at a[j]. After the loop, j points one step left of the gap; the key goes at a[j + 1].

Practice

1. Easy: Change the comparison to sort in descending order and trace {29, 10, 14, 37, 13}.
2. Harder: Write insertionSort(String[] names) that sorts names alphabetically using compareTo. Test it on {"Srihitha", "Navika", "Advitha"}.

Key Takeaways