# Insertion Sort

## In case you were wondering

This week I’m having a look at **Insertion sort**, another simple method to sort an array. In short, Insertion sort takes one value at the time, and checks it only compared to items to its left. If the item is smaller, it will be swap them until all the numbers to its left are smaller. This means that for each item, all the items to its left will already be sorted.

In practice at each iteration we are dividing the input in two separate arrays. The left array will always be sorted (a number on it’s own it’s sorted) and the right array is waiting to be sorted. We take the item with `index = 0`

, which goes in the sorted array and nothing else needs to be done. Then we take the item with `index = 1`

, which is were we actually start checking who’s bigger/smaller. The item that we compare with the left side of the array is called the **key**. The key gets compared to all items of the sorted array starting from the last, until the key is also sorted. Then we move to the next index of the initial array and the whole input is sorted. So each key is **inserted** in the sorted array, hence the name **Insertion sort**.

# In pseudo-code:

array = [several items]for (i = 1 to array.length) {

key = array[i]

j = i - 1

while (array[j] > key & j > 0){ // if array[j] is bigger

array[j+1] = array[j] // we move it up one space

j = j - 1

}

array[j+1] = key // we place our key in its sorted spot

}

# Example:

Let’s look at the `array = [4,2,5,3,1]`

.

We start sorting from `index = 1`

cause we for each item we need to be able to compare it to the item to its left.

Let’s take that element (2) and compare to the array made of the items to its left, which in this case is only made of one number (4). `2 < 4`

so the items are swapped. Now our `array = [2,4,5,3,1]`

. Let’s go through the rest of the array repeating the process until it’s completely sorted.

Iteration 1: comparing the element at `index = 1`

(2) with 4: [**4,2**,5,3,1] → [**2,4**,5,3,1]

Iteration 2: comparing the element at `index = 2`

(5) with 4: [2**,4,5**,3,1] → [2**,4,5**,3,1]

Iteration 3: comparing the element at `index = 3`

(3) with 5 and 4: [2**,**4,**5,3**,1] → [2**,4,3**,5,1] → [2**,3,4**,5,1]

Iteration 4: comparing the element at `index = 4`

(1) with 5, 4, 3 and 2: [2**,**3,4,**5,1**] → [2**,**3,**4,1**,5] → [2**,3,1**,4,5] → [**2,1**,3,4,5] → [1,2**,**3,4,5]

Notice how after each step, all the items to the left of the item that we are comparing are already sorted.

# In actual code:

`let insertionSort = (array) => {`

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

let key = array[i];

let j = i - 1;

while (j >= 0 && array[j] > key) {

array[j + 1] = array[j]

j = j - 1;

}

array[j + 1] = key;

}

return array;

}

Just before the end we assign the value of the key to input[j + 1] because array[j] corresponds to the first item in the sorted array whose value is less than the key’s value, so the key goes to the right of that.

Ta-dah!

That’s it, thanks for reading! Don’t forget to watch Insertion sort if it was Folk dance.