# Insertion Sort

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 