In this next series of Sorting Algorithms, I will be talking about **Insertion Sort**!

## What Is Insertion Sort?

Insertion Sort is a sorting algorithm that consumes an input element for each repetition and grows a sorted output. How this works is, at each iteration, the algorithm removes/ holds one element from the array, looks for the location it belongs to within the sorted list, and *inserts* that element back into the array at the correct sorted index.

### Pseudocode

- Start by picking the second element in the array.
- Compare the second element with the element before i. Swap if that second element is greater than the one before i.
- Continue to the next element, and if it is in the incorrect order, loop through the sorted portion, (the left side) to place that element in the current place.
- Repeat till array is sorted.

### The Code With Comments

```
function insertionSort(arr){
//start looping at first index
for(var i = 1; i < arr.length; i++){
//assign a plae holder varible at the index of i to keep track f the value we are looking at
var currentVal = arr[i]
//start working backwards with variable j at the value behind i
// ex: if i = 9, we want to start comparing the value of i to the value of j --> j = 77
//we need to keep going while j is greater than 0 (his up to the beginning of the array)
//and while j is greater than currentVal variable
for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
//ex: is currentVal = 9 smaller than arr[j] = 77 value, yes! then move arr[j] up in the array
//[2,4,5,20,77,77] 9 is waitning for its placement
arr[j + 1] = arr[j]
}
//after the loop is done, we have found our placement for currentVal
//we assign arr[j + 1] to currentVal b/c there will be a duplicate of arr[j] where it was before
// j
// [2,4,5,20,20,77] 9 waiting
// j+1 --> this is where 9 should be now
arr[j + 1] = currentVal
}
return arr
}
insertionSort([2,4,5,20,77,9])
```

### The Code Without comments

```
function insertionSort(arr){
for(var i = 1; i < arr.length; i++){
var currentVal = arr[i]
for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
arr[j + 1] = arr[j]
}
arr[j + 1] = currentVal
}
return arr
}
insertionSort([2,4,5,77,1,9])
```

### The Explanation

Now, if sorting algorithms have got your mind all boggled up, don't worry, I was the same way when I first started learning.

Basically, we want to iterate over the array with our variable i at the first index. *By first I mean the index of array[1]*. We then assign that element into a variable called **currentVal**.

Now we need to start thinking about how we will be moving backward in our array. We do this by iterating through our array again with a variable j **at the index behind i**. During this loop, if the current value is smaller than arr[j], we need to move it hold on to that value you, go down the list of elements, and find the index it belongs to.

```
for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
.....
}
```

Our j variable does this by shifting the larger value elements up in the array.

```
arr[j + 1] = arr[j]
```

Once we find that our currentVal variable is actually larger than an element at arr[j] we move up by one in the array and assign currentVal to that index

```
arr[j + 1] = currentVal
```

Finally, out of the loop, we can return the sorted array.

### Time & Space Complexity

The *best-case scenario* for a sorting algorithm like insertion sort is O(n).

We can obtain this during each iteration, the first remaining elements of the input is only compared with the right-most element of the sorted subsection f the array. This is achieved by using a while loop instead of a nested for loop.

Now, the *worst-case senario* for insertion sort is O(n^2), which is a quadratic running time. That is because, there is a nested for loop, which is looking through our array backward. Looking through and shifting the sorted subsection of the array before inserting the element into its right position.

### The Conclusion

Now, even though Insertion sort is much more efficient & faster than Bubble sort and Selection sort when it comes to small array lengths. It can not handle a large list of arrays. However, there are more advanced sorting algorithms that I will diving into next time on this series of **Sorting Algorithms**! So Stay tuned for the next blog post :)

Happy Coding!

## Top comments (0)