Insertion Sort

# Definition

Insertion sort is a sorting algorithm that moves each element in an array backwards until it finds its proper place. Insertion sort performs particularly well on small arrays and arrays that are almost ordered.

# Algorithm

2. If larger than the previous element, the element stays where it currently is.
3. If it is less keep checking elements to the left until the element we are sorting is greater than or equal the one to it's left while shifting each of the elements that are greater one space to the right.
4. Place the element in the vacant space.
5. Repeat steps 2-5 for each of the remaining elements in the array.

# Visual Insertion Sort # Code

```public static void insertionSort(int[] x){
int toSort = 0;
int position = 0;

for(int i = 1; i < x.length; i++){
toSort = x[i];
for (position = i-1; position >= 0 && toSort < x[position]; position--){
x[position+1] = x[position];
}
x[position+1] = toSort;
}
}
```

# Runtime

## Best Case

The best case scenario will occur when the array is already in correct order. In this case, the program will test each number against the one before it and find that it is already in the correct position, thus giving a runtime of O(n).

## Worst Case

The worst case scenario will occur when the array is in reverse order. Here, the program will have to move each element all the way back to the beginning of the array, thus giving a runtime of O(n2).