DEV Community

Tatyana Celovsky
Tatyana Celovsky

Posted on • Originally published at tatyanacelovsky.com on

2

Algorithm Series - Insertion Sort

Bright, multicolored paint cards are arranged in the shape of a hand fan on a white background. 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):

function insertionSort(array) {
for (let i = 1; i < array.length; i++) { // we assume that the first element of the array is already sorted and start iterating from the second element of the array;
let key = array[i]; // set next unsorted array element to equal key;
let j = i - 1; // set last sorted element to equal j;
while (j >= 0 && array[j] > key) { // check whether the current key is smaller than the last sorted element;
array[j + 1] = array[j]; // if it is, move the last sorted element to the right (making space for the current key);
j--; // move on to the next sorted element;
}
array[j + 1] = key; // if the current key is greater than the last sorted element, place it to the right of the last sorted element;
}
return array; // return the now sorted array.
}

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

Let’s Talk About Big-O

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay