FoundationSource checked

Insertion Sort

Sorts a list by inserting each item into the correct position within the already-sorted prefix.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Sorting
Difficulty: Beginner
Family: Incremental Sort
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 7
Code example: Ready
Visualization: Ready

Overview

Insertion Sort grows a sorted prefix one item at a time. For each new item, it shifts larger earlier items to the right and places the item into the gap.

Core Concepts

sorted prefixinsertion pointin-place shiftsstable ordering

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n^2)

Worst

O(n^2)

Space

O(1)

When to Use

Use it for small arrays or nearly sorted data.
Use it when a simple stable in-place sort is more important than asymptotic speed.
Use it as a base case inside hybrid sorts.

When Not to Use

Avoid it for large randomly ordered arrays.
Avoid it when many insertions would require long shifts through contiguous storage.

What It Does

Maintains a sorted prefix
Moves each item into the right place

Use Cases

Sorting small arrays
Sorting nearly sorted data
Finishing hybrid sorting algorithms

Inputs

Array or list of comparable values

Outputs

Sorted array or list

Pseudocode

1.Treat the first item as sorted
2.Take the next unsorted item
3.Shift larger sorted items one position right
4.Insert the item into the open position
5.Repeat until every item has been inserted

Canonical Example

Input: array = [5, 2, 4, 6]
Output: [2, 4, 5, 6]
Explanation: The algorithm inserts 2 before 5, then inserts 4 between 2 and 5, leaving 6 at the end.

Implementation Notes

Store the current key before shifting earlier items.
Keep the sorted-prefix invariant explicit: positions before the current index are already sorted.
Test empty, one-item, sorted, reverse-sorted, and duplicate-heavy arrays.