# Insertion Sort

Insertion sort is an algorithm used to sort an unordered array of items.

Given an unsorted array `arr`

, insertion sort builds up an array of sorted elements “in-place”.

Visualize sorting an unsorted `deck`

of cards. Take off the first card and put it into a `sorted`

pile. Then take the next card `key`

off the deck.

Compare `key`

with each card in the `sorted`

pile from greatest to least, until you find the card which `key`

is greater than. Insert `key`

there. Continue until `deck`

is empty.

Or, in array-speak, for each element `key`

in the original array, excluding the first and the last, we:

Test `key`

against all preceding elements from indices `(i...0]`

- is
`key`

smaller than the element?- shift
`arr[j]`

forward by one to`j+1`

- this duplicates j in the array. the duplicate will be overwritten in the next loop, either with the adjacent smaller element or, if we find the position for
`key`

, with`key`

itself - decrease
`j`

by one

- this duplicates j in the array. the duplicate will be overwritten in the next loop, either with the adjacent smaller element or, if we find the position for

- shift
- is
`key`

larger than`arr[j]`

(or are we at the beginning of the array,`j===0`

)?- we have found the position for
`key`

! insert`key`

at`j+1`

- we have found the position for

The code looks like this:

```
function insertionSort(arr) {
for (var i = 1; i < arr.length; i++) {
let key = arr[i];
console.log(i, key);
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
```

### What the…?

It’s tough to visualize. Let’s take it step by step in sorting `var arr = [3,2,1]`

with length 3.

#### i is 1, key is `arr[i] => 2`

`j===0`

. `arr[0]===3`

.

`3>2 && j>=0`

is true, so we execute the while loop body.`arr[0+1]=arr[0]`

`j--`

The array now looks like this: `[3,3,1]`

`j===-1`

. `arr[0]===4`

.

`-1>=0`

is false. We do not execute the while loop body.- Instead, we replace
`arr[j+1]`

(`arr[0]`

) with`key`

.

The array now looks like this: `[2,3,1]`

- i++

#### i is 2, key is `arr[2] => 1`

`j===1`

. `arr[1]===3`

.

`3>1&&j>=0`

is true, so we execute the while loop body.`arr[1+1]=arr[1]`

`j--`

The array now looks like this: `[2,3,3]`

`j===0`

. `arr[0]===2`

.

`2>1 && j>=0`

is true, so we execute the while loop body.`arr[1+1]=arr[1]`

`j--`

The array now looks like this: `[2,2,3]`

`j===-1`

. `arr[0]===4`

.

`-1>=0`

is false. We do not execute the while loop body.- Instead, we replace
`arr[j+1]`

(`arr[0]`

) with`key`

.

The array now looks like this: `[1,2,3]`

- i++

#### i is 3. `3<3`

is false

We exit the for loop and return the sorted array, `[1,2,3]`

.