Introduction

Insertion sort is an in-place comparison-based sorting algorithm that builds a sorted array one element at a time. Instead of repeatedly finding the minimum or maximum element across the entire collection, it takes each element from the unsorted portion and inserts it into its correct relative position within an expanding sorted portion.

How Insertion Sort Works

Shifting vs. Swapping

Many elementary sorts use full pairwise swaps to move elements. Insertion sort optimizes this by shifting elements instead:

1. Store the value of the current unsorted element in a variable (currentValue).
2. Iterate backward through the sorted portion starting from i - 1.
3. As long as an element in the sorted portion is greater than currentValue, shift that element one position to the right (array[j + 1] = array[j]).
4. Once an element less than or equal to currentValue is reached (or the beginning of the array is reached), place currentValue into the vacant index (array[j + 1] = currentValue).

Implementing Insertion Sort

Algorithm outline

1. Start looping from index 1 to the end of the array (the element at index 0 is already sorted).
2. Store the current value: currentValue = array[i].
3. Initialize an inner pointer j = i - 1.
4. While j >= 0 and array[j] > currentValue:
   • Shift the larger element right: array[j + 1] = array[j].
   • Decrement j.
5. Place currentValue into its sorted position: array[j + 1] = currentValue.
6. Return the sorted array.

Implementation

const insertionSort = (array) => {
  for (let i = 1; i < array.length; i++) {
    const currentValue = array[i];
    let j = i - 1;

    // Shift elements of the sorted portion that are greater than currentValue
    while (j >= 0 && array[j] > currentValue) {
      array[j + 1] = array[j];
      j--;
    }

    // Place currentValue into its correct spot
    array[j + 1] = currentValue;
  }

  return array;
}

Examples

Basic usage

const numbers = [2, 1, 9, 76, 4];
console.log(insertionSort(numbers)); // [1, 2, 4, 9, 76]

const dataset = [3, 44, 38, 5, 47, 15];
console.log(insertionSort(dataset)); // [3, 5, 15, 38, 44, 47]

Evaluating Insertion Sort

Complexity analysis

When Insertion Sort Excels

1. Nearly sorted data

When data is already mostly sorted (e.g., [1, 2, 3, 4, -1]), insertion sort only performs work for the few elements out of place. Most elements trigger an immediate break in the inner loop, achieving near-linear $O(n)$ performance.

2. Online algorithms and live data streams

An online algorithm is one that can process input piece by piece as it arrives, without requiring the entire dataset upfront.

Because insertion sort continuously maintains a fully sorted portion on the left side of an array, newly received data points can be inserted directly into their correct position immediately upon arrival.

Existing sorted collection:  [10, 20, 30, 40]
New live number arrives:      25
Insert into sorted position: [10, 20, 25, 30, 40]

Key Takeaways

• Expanding Sorted Portion: Insertion sort builds the sorted array incrementally from left to right, maintaining an always-sorted region at the front.
• Shifting Over Swapping: Rather than performing costly multiple swaps, it copies larger elements one slot to the right and inserts the target value directly into the resulting opening.
• Adaptive Linear Best Case: On already sorted or nearly sorted arrays, insertion sort runs in $O(n)$ time because the inner loop stops after a single comparison.
• Online Processing: Its ability to place new items into an existing sorted section makes it well suited for continuous, streaming, or real-time data inputs.
• In-Place and Lightweight: Requires only $O(1)$ auxiliary space, modifying the array directly.