Insertion Sort

Insertion

Sorts by building a final sorted array one item at a time, inserting it into place.

Adaptive

Performance improves significantly on data that is already partially sorted.

In-Place

Requires a constant amount of extra memory space (O(1)), regardless of input size.

Stable

Preserves the relative order of elements with equal values.

Insertion Sort is an intuitive, comparison-based algorithm that builds a final sorted array one element at a time. It works much like sorting a hand of playing cards: you iterate through the elements, picking up one at a time and inserting it into its correct position within the already-sorted part of the list.

Visualize Fullscreen

Demo

20 elements • 4x Speed

No Data

Did you know?

The algorithm's mechanism is very similar to how many people manually sort a hand of playing cards.
Due to its high efficiency on small lists, Insertion Sort is often used as a subroutine in more advanced hybrid algorithms like Timsort (used in Python and Java) and Introsort.
The number of swaps the algorithm performs is equal to the number of inversions in the array (pairs of elements that are out of order).

How it Works

Assume the first element is a sorted sub-array of size one.
Pick the next unsorted element. This is your key.
Compare the key with the elements in the sorted sub-array, moving from right to left.
Shift all elements in the sorted sub-array that are greater than the key one position to the right. This opens up a gap.
Insert the key into this gap. The sorted sub-array is now one element larger.
Repeat this process until all elements have been inserted into the sorted sub-array.

Complexity Analysis

Best Case

O(n)

Average

O(n^2)

Worst Case

O(n^2)

Space

O(1)

Advantages

Simplicity: Very easy to understand and implement, making it great for educational purposes.
Efficient on Small Data: Outperforms more complex algorithms for small or nearly-sorted arrays.
Adaptive: Has a linear time complexity of $O(n)$ if the input array is already sorted.
Stable: Preserves the relative order of elements that have equal values.
In-place: Requires only a constant $O(1)$ amount of additional memory space.

Disadvantages

Inefficient for Large Datasets: Its $O(n^2)$ average and worst-case time complexity makes it very slow for large, randomly ordered lists.
Quadratic Worst-Case: Performance degrades significantly on reverse-sorted data, which represents its worst-case scenario.

Implementation

JavaScript insertion-sort.js

function insertionSort(arr) {
  // Start from the second element (arr[0] is trivially sorted)
  for (let i = 1; i < arr.length; i++) {
    // The element to be inserted into the sorted portion
    let key = arr[i];
    
    // Index of the last element in the sorted portion
    let j = i - 1;

    // Move elements of arr[0..i-1] that are greater than key
    // one position ahead of their current position.
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    
    // Insert the key into its correct position
    arr[j + 1] = key;
  }
  return arr;
}