Insertion Sort

Insert an element into the finished part

Insertion sort treats the first element as a sorted prefix, then takes the next element and inserts it into the proper position on the left. To make room, larger elements of the prefix are shifted one position to the right.

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int value = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > value) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = value;
    }
}

The value in value is temporarily stored separately. While elements larger than it appear on the left, they are shifted to the right. When the loop stops, j + 1 is the insertion position. After every iteration, the range from 0 through i is fully sorted.

Why nearly sorted data is convenient

If elements are already close to their final positions, the inner loop performs only a few shifts. For a completely sorted array, the condition a[j] > value is immediately false at every step, so the running time becomes O(n).

On average and in the worst case, insertion sort takes O(n²) time and uses O(1) extra space. For small or nearly sorted arrays, it can still be practical because its overhead is very small.