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 && a[j-1] > 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.