Insertion Sort

Time complexity: O(n²)

Space complexity: O(1)

Data type: Arrays, Linked Lists

Visualization

Comparisons: 0

Reorders: 0

Delay: 1ms

Items: 50

Definition

Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by iteratively consuming one input element and inserting it into its correct position within the sorted portion of the array. The algorithm is efficient for small datasets and nearly sorted arrays.

Constraints

  • Inefficient for large random datasets due to O(n²) time complexity
  • Excellent performance for small arrays (typically n ≤ 10)
  • Highly efficient for nearly-sorted or already-sorted data (O(n))
  • Often used as the base case for hybrid sorting algorithms

Step-by-step explanation

Arguments:

  • Array to be sorted - array
  • Current key element being inserted - key
  • Index for sorted portion - j
  • Boundary between sorted/unsorted portions - i

Explanation:

  • Start with the second element (index 1) as the initial key
  • Compare the key with elements in the sorted portion (to its left):
    • Shift elements greater than the key one position right
    • Continue until finding an element ≤ key or reaching array start
  • Insert the key into its correct position in the sorted portion
  • Move to the next unsorted element and repeat the process
  • After each iteration, the sorted portion grows by one element
  • Algorithm completes when all elements are processed

Returns:

Returns nothing (sorts array in-place)
Modifies the original array instead of returning a new one
No explicit return value (void function in most implementations)

Example

1
#include <vector>
2
#include <iostream>
3


4
void insertionSort(std::vector<int>& arr) {
5
    int n = (int)arr.size();
6
    for (int i = 1; i < n; ++i) {
7
        int key = arr[i];
8
        int j = i - 1;
9


10
        // Move elements greater than key one position ahead
11
        while (j >= 0 && arr[j] > key) {
12
            arr[j + 1] = arr[j];
13
            --j;
14
        }
15


16
        arr[j + 1] = key;
17
    }
18
}