DSA AnimatorDSA animations
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 (Lifted) 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.

How to solve Insertion Sort

LeetCode 912 · Easy · Sorting Algorithms · Pattern: Insert into Sorted Prefix

Why the obvious approach is slow

It is O(n²) in the worst case. But on nearly sorted data it is very fast, which is why libraries use it for small parts.

The key idea

Keep the left part of the array sorted. Take the next value as the key. Shift every bigger value in the sorted part one step to the right. Drop the key into the gap that opens up. Repeat until the whole array is the sorted part.

Remember

Shift bigger values right, then drop the key into the gap. Insertion sort shines on small or nearly sorted inputs.

Run the animation above on your own input, or watch the 1:36 video explanation of Insertion Sort with a dry run and Java code.

More Sorting Algorithms problems