Insertion sort

Using insertion sort, the elements are transferred one at a time to the right position. In other words, insertion sort creates the sorted array one item at a time using a ranking comparison of sorts.

Implementation

Below we can see an example implementation of insertion sort using JavaScript.

function insertionSort(input) {
  const output = [...input];

  for (let index = 1; index < output.length; index++) {
    let key = output[index];
    let inner = index - 1;

    while (inner >= 0 && output[inner] > key) {
        output[inner + 1] = output[inner];
        inner = inner - 1;
    }

    output[inner + 1] = key;
  }

  return output
}

We begin by cloning the input array and looping over each item beginning at index 1. We get the item at index 1 and assign it to a key variable, then we create an inner variable which will, on the first iteration, be equal to 0. The inner loop is then executed and checks if the inner item is larger than the key, if it is, we shift it to the right and if it isn't, we exit the loop using the inner as a circuit breaker. Next we assign the key to one position to the right, essentially as a pivot. In essence the outer loop looks left to right and the inner loop goes right to left from the current index minus 1, comparing items. Finally we return the output array.

Use Case and Performance

Insertion sort has a Big O time complexity of O(n²) on average. This means that the time it takes to run the algorithm is the square of the size of the input array, otherwise known as Quadratic Time.

Let's look at some example runtimes from given input sizes:

In general, insertion sort has a similar set of use cases as bubble sort and selection sort due to the time complexity. This means that it is best used on small to medium sized collections rather than large datasets.