Insertion sort is a very simple sorting algorithm. It runs in O(N^2) time, which is not great as most good sorting algorithms run in O(n * lg(n)) time.

It does turn out to be a very useful though in practice because:
– It is quite efficient on small lists.
– It is stable (won’t change the relative position of elements that are the same sort value).
– It is very efficient on mostly sorted lists.
– It requires no additional memory.

The algorithm is very simple if you think about it this way:
– Iterate “i” from index 1 (0 based) to length – 1.
– In a nested loop, move from “i” backward, swapping the element from “i” downward until it is in its proper place.

import java.util.Arrays;

public class InsertionSort {
    public static void sort(int[] a) {
        int i = 1;
        while (i <a> 0 &amp;&amp; a[j-1] &gt; a[j]) {
                int tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
                j--;
            }
            ++i;
        }
    }

    public static void main(String[] args) {
        int a[] = new int[] {7, 2, 9, 1, 6, 3, 4, 5, 8};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

Output

[7, 2, 9, 1, 6, 3, 4, 5, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Visualization

Image taken from https://en.wikipedia.org/wiki/Insertion_sort#/media/File:Insertion_sort.gif.