Sorting With Insertion Sort

7th Nov 2021
A wooden drawer


Insertion sort works similar to how most people would sort a hand of playing cards. You pick up the first card from a face-down deck of cards and put it in your left hand. Picking up the next card, you compare it, from left to right, with the cards already sorted in your left hand and insert it in its correct place. The cards in the left hand are sorted at all times.

The Algorithm

Input: A sequence of nn numbers: (a1,a2,...,an)(a1, a2, ..., an)

Output: A permutation (reordering) (a1,a2,...,an)(a'1, a'2, ..., a'n) of the input sequence such that a1<=a2<=...<=ana'1 < = a'2 < = ... < = a'n

  • The numbers to sort are also known as keys.

  • The input array is sorted in place

Implementation in JavaScript

function insertionSort(arr) {
  for (let j = 1; j < arr.length; j++) {
    const key = arr[j]
    let i = j - 1

    while (i >= 0 && arr[i] > key) {
      arr[i + 1] = arr[i]
      i = i - 1
    arr[i + 1] = key
  return arr

Running Time

The running time of insertion sort is: O(n2)O(n^2)

Insertion sort is very efficient for small arrays (7 - 50) elements.