[Elementary Sorting Algotithms] Insertion sort

Builds up the sort by gradually creating a larger left half which is always sorted

 

[5, 3, 4, 1, 2]

[3, 5, 4, 1, 2]

[3, 4, 5, 1, 2]

[1, 3, 4, 5, 2]

[1, 2, 3, 4, 5]

 

visualgo | insertion sort

 

Pseudocode

• start by picking the second element in the array
• now compare the second element with the one before it and swap if necessary
• continue to the next element and if it is in the incorrect order, iterate through the sorted portion(eg.the left side)to place the element in the correct place
• repeat until the array is sorted

Implementation

function insertionSort(arr) {
  for (let i = 1; i < array.length; i++) {
    let currentVal = arr[i];
    for (let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = currentVal;
  }
  return arr;
}

insertionSort([2, 1, 9, 76, 4]);

 

Big O complexity

it can perform at O(n) in the best case (if almost sorted)

it performs at O(n2) in the average and worst case.