Insertion Sort

Insertion Sort is a simple sorting algorithm that builds a sorted array one element at a time. It works by taking each element and inserting it into its correct position within the already sorted portion of the array.

It is efficient for small datasets and performs well when the array is already partially sorted, but it is not suitable for large datasets.

How It Works

Insertion Sort works by gradually expanding a sorted section:

Start with the second element (the first is considered sorted).
Compare the current element with the one before it.
If the current element is smaller, shift the larger element to the right.
Continue comparing and shifting until the correct position is found.
Insert the element into its correct position.
Move to the next element and repeat.

This process continues until all elements have been placed in their correct positions.

JavaScript Example


function insertionSort(arr) {
  const result = [...arr];

  for (let i = 1; i < result.length; i++) {
    const current = result[i];
    let j = i - 1;

    while (j >= 0 && result[j] > current) {
      result[j + 1] = result[j];
      j--;
    }

    result[j + 1] = current;
  }

  return result;
}

// Example usage
const values = [8, 3, 5, 2, 9];

console.log(insertionSort(values)); // [2, 3, 5, 8, 9]