## CodeNewbie Community is a community of 5,788 amazing newbies

Tatyana Celovsky

Posted on • Originally published at tatyanacelovsky.com on

# Algorithm Series - Insertion Sort

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:

1. Assume that the first element of the array is property sorted;
2. Store the second element of the array in a `key`;
3. Compare `key` to the first element - if `key` is smaller that the first element, then `key` is placed in front of the first element;
4. Store the next unsorted element of the array in a `key`;
5. 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;
6. 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.

### Resources

Insertion Sort Algorithm gist