Previous Topic

What Is Insertion Sort?

Insertion sort is a straightforward sorting algorithm that processes a collection (often an array or list) from left to right, maintaining a growing sorted prefix. For each element, it finds the correct position within the already-sorted portion and inserts it there, shifting larger elements to the right as needed.

How It Works

1. Assume the first element is trivially sorted.
2. Pick the next element (the "key").
3. Scan left through the sorted portion, shifting elements that are greater than the key one position to the right.
4. Insert the key into the first position where it is not less than the element to its left.
5. Repeat until all elements are processed.

Example

Given [5, 2, 4, 6, 1, 3]:

• Start with [5] | [2, 4, 6, 1, 3]
• Insert 2: [2, 5] | [4, 6, 1, 3]
• Insert 4: [2, 4, 5] | [6, 1, 3]
• Insert 6: [2, 4, 5, 6] | [1, 3]
• Insert 1: [1, 2, 4, 5, 6] | [3]
• Insert 3: [1, 2, 3, 4, 5, 6]

Pseudocode

for i from 1 to n-1:        # 0-based indexing
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j + 1] = A[j]
        j = j - 1
    A[j + 1] = key

Properties and Complexity

• In-place: Yes (O(1) extra space)
• Stable: Yes (equal elements keep their relative order)
• Adaptive: Yes (runs fast on nearly sorted data)
• Online: Yes (can sort as elements arrive)
• Time complexity:
  • Best case (already sorted): O(n)
  • Average case: O(n^2)
  • Worst case (reverse sorted): O(n^2)
• Space complexity: O(1) auxiliary space

When to Use It

• Small arrays or lists (often used as a base case in hybrid sorts)
• Nearly sorted data where few shifts are needed
• Streaming or interactive scenarios (online sorting)
• When stability matters and dataset size is modest

Variants and Related Ideas

• Binary insertion sort: Uses binary search to find the insertion point (still O(n^2) due to shifts).
• Shell sort: Generalizes insertion sort by comparing elements far apart, improving performance.
• Hybrid algorithms: Many library sorts switch to insertion sort for small subarrays.

Implementations

Python

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

JavaScript

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

Common Pitfalls

• Forgetting to handle the left boundary (j can go to -1).
• Not preserving stability by using the wrong comparison when equal (use > rather than >= when shifting).
• Expecting good performance on large, random datasets (it will be O(n^2)).

Practice Ideas

• Modify the implementation to count shifts and comparisons.
• Implement binary insertion sort and compare run times.
• Use insertion sort as a base case within merge sort or quicksort for small subarrays.

Next Topic