# Insertion Sort

Insertion sort is a simple sorting algorithm which can be used to sort an array lowest to highest, which is what I have done. It works by comparing two numbers next to each other, if the one on the right is bigger it will store that number and loop through the array, comparing that number to each number in the array checking if it is smaller then any, if it is, it will swap them and it will keep swapping them until it is larger then the number on the left.

How I did this in Java is by having a loop which is forwarded by one:

public int[] inserstionSort(int[] array) {

if (array.length < 1) return array;

for (int i=1; i < array.length; i++) {

}

return array;

}

Then a nested loop which was behind by 1 and counting down while the first loops number is smaller then the current number:

public int[] inserstionSort(int[] array) {

if (array.length < 1) return array;

for (int i=1; i < array.length; i++) {

int temp = array[i];

int j;

for (j=i-1; j >= 0 && temp < array[j]; j--) {

}

}

return array;

}

And of course since it was smaller we must swap them:

public int[] inserstionSort(int[] array) {

if (array.length < 1) return array;

for (int i=1; i < array.length; i++) {

int temp = array[i];

int j;

for (j=i-1; j >= 0 && temp < array[j]; j--) {

array[j + 1] = array[j];

}

array[j + 1] = temp;

}

return array;

}

This algorithm can be faster then selection sort. Its O notation for worst case is 0(n²) which is very slow and the same as selection sort. But in its best case it can be 0(n) which is not amazing but it is defiantly faster then o(n²). This algorithms space complexity (memory usage) is good, it is 0(1) which means the algorithm is constant.