## DEV Community is a community of 665,497 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Sorting Algorithms: Insertion Sort keeks5456
Full-stack Software Engineer

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.

``````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])
``````

``````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. 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!