DEV Community

Atila Fassina
Atila Fassina

Posted on • Originally published at atila.fassina.eu on

Insertion Sort in JS

What it is

It‘s a simple to implement sort algorithm. In a nutshell, Insertion Sort iterates twice through the array. First iteration corresponds to the target position, whilst second iteration is for comparison with future elements. Every time the current item is smaller than the comparison value, it is inserted in the current position and first iteration moves forward.

When to use it

not very efficient for large data sets, but quite efficiente and powerful for small ones. It can avoid confusion by not changing the order of equal set of keys.

const insertionSort = (unsortedList: []) {

  // First iteration:
  // get the target position
  for (let i = 1; i < unsortedList.length; i++) {
    const currentItem = unsortedList[i]
    let j

    // Second iteration:
    // compare elements, assign each to new sorted position
    for (j = i; j > 0 && currentItem < unsortedList[j - 1]; j--) {
      unsortedList[j] = unsortedList[j - 1]
    }

    unsortedList[j] = currentItem
  }

  return unsortedList
}

Shameless plug

I have a personal playground where I plan to implement some Computer Science basics in JavaScript. With good test coverage and some insights on when/why to use each concept. Check out my insertion sort implementation at the FUNdamentals repository.

Top comments (0)