Insertion Sort
Insertion Sort is a simple, comparison-based sorting algorithm that builds the final sorted array one element at a time. It takes each element from the unsorted part and slides it into its correct position in the sorted part. It is like placing a new card in the right spot of a sorted hand, making it intuitive and efficient for small datasets. Like Bubble Sort, Insertion Sort is a O(n²) algorithm, but it performs significantly better on nearly sorted data.
Pseudocode
for i = 1 to (n - 1):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
Visualizer
Select number of elements:
How It Works
Insertion Sort starts with the second element in the array (considering the first element as already sorted). It picks this "key" element and compares it with the elements to its left. If any of those elements are larger than the key, they are shifted one position to the right. The key is then inserted into the gap created by the shifting. This process repeats for each subsequent element until the entire array is sorted. Because the algorithm only moves elements when necessary, it is particularly efficient when the input data is already mostly sorted.
When to Use
Insertion Sort is ideal for small datasets, nearly sorted arrays, or as a finishing step inside more complex algorithms like Timsort (Python's built-in sort). Many hybrid sorting algorithms switch to Insertion Sort for small sub-arrays because its low overhead and cache-friendly access patterns outperform divide-and-conquer algorithms at that scale.
Time & Space Complexity
Metric / Operation | Complexity | Description |
|---|---|---|
| Best Case | O(n) | When the array is already sorted, each element is compared once and no shifting is needed. |
| Average Case | O(n²) | On average, each element must be compared with about half of the elements already in the sorted portion. |
| Worst Case | O(n²) | When the array is sorted in reverse order, every element must be compared with all previously sorted elements. |
| Space Complexity | O(1) | Insertion Sort is an in-place algorithm that sorts by shifting elements within the original array. |
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0.