🧠

Insertion Sort

Insertion sort animation

  • Builds sorted list one item at a time
  • Less efficient on large lists compared to other algorithms

Complexity

Average Time Space
O(n2)O(n^2) 11

Process

  • Keep front of the list sorted
  • Loop through unsorted elements
  • Place them in proper position in sorted elements

Implementations

JavaScript

function insertionSort(array) {
  // Loop through all elements in the array
  for (let i = 0; i < array.length; i++) {
    let currIndex = i;

    // If the previous element is greater than the current we swap
    while(array[currIndex - 1] !== undefined && array[currIndex] < array[currIndex - 1]) {
      // Swap the elements
      [array[currIndex - 1], array[currIndex]] = [array[currIndex], array[currIndex - 1]];

      // Shift the current index back
      currIndex--;
    }
  }

  return array;
}

Computer Science Algorithm

Backlinks