← Back to DSA Animator
Insertion Sort LC #912 Easy Insertion Sort
Problem

Given an array of integers nums, sort the array in ascending order using the Insertion Sort algorithm — build up a sorted prefix one element at a time by inserting each new element into its correct position among the already-sorted elements to its left.

Example 1
Input: nums = [8,4,3,7,6]
Output: [3,4,6,7,8]
Constraints: 1 ≤ n ≤ 5*10^4  |  -5*10^4 ≤ nums[i] ≤ 5*10^4
Try Examples
Custom:
Approach
Grow a Sorted Prefix, Insert Each New Element
For i=1..n-1, save key=nums[i], then walk left shifting every element greater than key one step right until the correct gap is found, and drop the key in. The sorted prefix nums[0..i-1] grows by one each iteration. O(n) best case (already sorted), O(n²) average/worst, O(1) space.
Array
Comparing Shifting Key Sorted
nums[] — current state
Variables
i
—
j
—
comparisons
0
shifts
0
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Start with nums[0] as the trivially sorted prefix
2
For i = 1..n-1, save key = nums[i]
3
Shift elements greater than key one step right
4
Insert key at the gap — sorted prefix grows by one
Best
O(n)
Avg/Worst
O(n²)
Space
O(1)
Why It Works

Invariant: before processing index i, nums[0..i-1] is always sorted. We pull nums[i] out as key, then repeatedly shift the sorted prefix's elements one step right wherever they exceed key, opening a gap that walks left. As soon as we hit an element ≤ key (or run off the front), the gap is key's correct resting spot — dropping it in there keeps nums[0..i] sorted, extending the invariant by one. On already-sorted input, the inner loop never shifts, giving the O(n) best case.