# Insertion Sort

```
function sort (arr) {
const len = arr.length;
for (let i = 1; i < len; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j = j - 1;
}
arr[j+1] = key;
}
return arr;
}
```

## How it works

- grab an item from a set
- insert it in the result array
- grab a new item from the set
- find where it fits in the result array
- insert it there
- repeat steps 3-5 until no more items in the original set

## Info

- simple to implement algorithm
- builds the resulting sorted array one item at a time
- efficiency/speed
- slower than quick/heap/merge sort
- faster than selection/bubble sort
- caveat:
- fast on very small arrays
- faster than quicksort
- good quicksort implementations will default to insertion sort when the array is under a certain threshold

- fast on already sorted arrays
- not all sorting algorithms are

- best case O(n)
- worst case O(n^2)
- average case O(n^2)

- memory
- O(1)
- only requires a constant amount of memory

- is a quadratic sorting algorithm
- stable
- this means that it doesnâ€™t change the order of elements with equal keys

- online
- means it can sort one at a time, rather than needing the whole set up front

- can be done in place by just keeping track of which part of the array is already sorted (assuming a mutable array)