Photo by Dee @ Copper and Wild on Unsplash

*This is a quick tutorial on the Insertion Sort algorithm and its implementation in Javascript.*

### What is Insertion Sort Algorithm

Insertion Sort is a sorting algorithm that places the element in its appropriate place based on the sorting order. A good example of Insertion Sort is sorting cards held in your hands during a card game.

Let’s take a look at Insertion Sort when trying to sort the elements of an array in an ascending order:

- Assume that the first element of the array is property sorted;
- Store the second element of the array in a
`key`

; - Compare
`key`

to the first element - if`key`

is smaller that the first element, then`key`

is placed in front of the first element; - Store the next unsorted element of the array in a
`key`

; - Compare
`key`

to the sorted element and place it in the appropriate place with respect to the sorted elements based on whether`key`

is smaller or greater than each of the sorted elements; - Continue with steps 4 and 5 until all elements of the array are sorted.

The array is sorted when all the unsorted elements are placed in their correct positions.

### Insertion Sort Code in Javascript

Let’s take a look at the code for the Insertion Sort algorithm described above (ascending order):

Let’s take a look at the code for the Insertion Sort algorithm described above (ascending order):

### Insertion Sort and Big-O

Insertion Sort compares the adjacent elements, hence, the number of comparisons is:

(n-1) + (n-2) + (n-3) +…..+ 1 = n(n-1)/2

This nearly equals to n2, therefore Big-O is O(n²) or quadratic time. We can also deduce this from observing the code: insertion sort requires two loops, therefore Big-O is expected to be O(n²).

### Conclusion

Insertion Sort inserts each element of the array in its appropriate place based on whether the array is being sorted in ascending or descending order. It is a simple way to sort a list when complexity does not matter and the list that needs sorting is short.

## Discussion (0)