CPKit
v1.6.1

Insertion Sort

SortingEasy

Insert each element into its correct relative position within the sorted prefix partition.

Alt+Shift+I

Configuration Panel

Shift / Insert Visualizer

23
0
8
1
56
2
12
3
38
4
5
5
72
6
16
7
Step: 1 / 1

Time Complexity

O(N^2) worst/average, O(N) best case (for sorted inputs)

Space Complexity

O(1) auxiliary variables
Conceptual Overview

Insertion Sort builds the final sorted array one item at a time by placing each new element into its correct relative position within the already-sorted prefix partition.

Algorithm Idea

Iterate from index 1 to N-1. Save the key element. Shift all sorted elements larger than key to the right, then insert the key into the vacant slot.

Stable Sorting

Stable (does not change order of equal elements during shifts)

In-place Memory

In-place (requires no extra memory)

Source: CP-Algorithms search & sorting reference