Loading…

easyBasicsSometimes asked

Insertion Sort

Basics · 6 min

Given an integer array nums, sort it ascending using insertion sort (in place).

In plain English

Grow a sorted prefix by inserting each next element into its correct spot, shifting larger elements right.

Examples

Example 1

Input: nums = [3, 1, 2]
Output: [1, 2, 3]
Note: Sorted.

Example 2

Input: nums = [1, 2, 3]
Output: [1, 2, 3]
Note: Already sorted → O(n).

Example 3

Input: nums = [2, 1]
Output: [1, 2]
Note: One insert.

Constraints

0 ≤ nums.length ≤ 10^3

Clarifying questions1First question: Is the data likely nearly sorted?Explore questions

Q1.Is the data likely nearly sorted?
If so insertion sort is an excellent O(n)-ish choice.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

For each element, shift the larger elements of the sorted prefix one step right and drop the element into the gap. O(n²) worst, O(n) on nearly-sorted input.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you implement shift-and-insert and know its adaptivity to sorted input.

Where candidates slip

Losing the key by not saving it, or an off-by-one placement.

How to stand out

Note it's stable, adaptive (O(n) on sorted), and used inside Timsort.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Shift-and-insert

TimeO(n²)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Treat the left part as sorted — where does the next element belong?

2Hint 2Explore hint

Shift larger sorted elements right to open a gap, then insert the key.

3Hint 3Explore hint

What happens on already-sorted input?

A · Core idea

Insertion sort grows a sorted prefix by taking each next element (the 'key') and shifting the larger sorted elements one step right to open a slot, then dropping the key in.

Why it's great on nearly-sorted data. If the key is already ≥ the prefix's last element, no shifting happens — so on an (almost) sorted array each insertion is O(1), giving near-linear O(n) total. This adaptivity is its real strength and why it's used as the base case inside fast sorts (e.g. Timsort).

Why save the key first. The shifting overwrites positions, so you must capture key = nums[i] before sliding elements, then place it in the opened gap at j+1.

Stable, in place, O(n²) worst. On reverse-sorted input every element shifts the whole prefix → O(n²); but it's stable and O(1) space.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 1, 2]

key=1

shift 3 right, insert 1

State[1,3,2]

Final result[1, 2, 3]

C · Code with teaching comments

solution.javaJava

Shift-and-insert — optimal

2 teaching notes

1
public void insertionSort(int[] nums) {
2
    for (int i = 1; i < nums.length; i++) {
3
        int key = nums[i];
4
        int j = i - 1;
5
        while (j >= 0 && nums[j] > key) {
6
            nums[j + 1] = nums[j];
7
            j--;
8
        }
9
        // Drop the key into its correct position.
10
        nums[j + 1] = key;
11
    }
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — worst case shifts the whole prefix each time → O(n²); on nearly-sorted data few shifts → O(n).

E · Edge cases and pitfalls5nums = [1, 2, 3] — Already sorted → O(n), no shifts.Explore edge cases

Edge cases handled

nums = [1, 2, 3]Already sorted → O(n), no shifts.
nums = [2, 1]One insert → [1, 2].
nums = [3, 2, 1]Reverse → worst-case O(n²).

Pitfalls

Overwriting the key before shifting (save it first).
Off-by-one when placing the key (j+1).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void insertionSort(int[] nums) { for (int i = 1; i < nums.length; i++) { int key = nums[i]; int j = i - 1; while (j >= 0 && nums[j] > key) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Overwriting the key before shifting (save it first).
Off-by-one when placing the key (j+1).

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Shift-and-insert

Code pattern to memorize

for i: key=a[i]; shift a[j]>key right; a[j+1]=key

Rules to remember

1Sorted prefix grows.
2Shift larger elements right.
3Fast on nearly-sorted data.

Use this pattern when

Nearly-sorted data
Base case of hybrid sorts

Interview takeaway

Insertion sort shines when the data is almost sorted.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Shift-and-insert. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Bubble Sort
Another O(n²) stable sort with early exit.

Same pattern

easyBasicsSometimes asked

Insertion Sort

Basics · 6 min

Given an integer array nums, sort it ascending using insertion sort (in place).

In plain English

Grow a sorted prefix by inserting each next element into its correct spot, shifting larger elements right.

Examples

Example 1

Input: nums = [3, 1, 2]
Output: [1, 2, 3]
Note: Sorted.

Example 2

Input: nums = [1, 2, 3]
Output: [1, 2, 3]
Note: Already sorted → O(n).

Example 3

Input: nums = [2, 1]
Output: [1, 2]
Note: One insert.

Constraints

0 ≤ nums.length ≤ 10^3

Clarifying questions1First question: Is the data likely nearly sorted?Explore questions

Q1.Is the data likely nearly sorted?
If so insertion sort is an excellent O(n)-ish choice.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

For each element, shift the larger elements of the sorted prefix one step right and drop the element into the gap. O(n²) worst, O(n) on nearly-sorted input.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you implement shift-and-insert and know its adaptivity to sorted input.

Where candidates slip

Losing the key by not saving it, or an off-by-one placement.

How to stand out

Note it's stable, adaptive (O(n) on sorted), and used inside Timsort.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Shift-and-insert

TimeO(n²)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Treat the left part as sorted — where does the next element belong?

2Hint 2Explore hint

Shift larger sorted elements right to open a gap, then insert the key.

3Hint 3Explore hint

What happens on already-sorted input?

A · Core idea

Insertion sort grows a sorted prefix by taking each next element (the 'key') and shifting the larger sorted elements one step right to open a slot, then dropping the key in.

Why save the key first. The shifting overwrites positions, so you must capture key = nums[i] before sliding elements, then place it in the opened gap at j+1.

Stable, in place, O(n²) worst. On reverse-sorted input every element shifts the whole prefix → O(n²); but it's stable and O(1) space.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 1, 2]

key=1

shift 3 right, insert 1

State[1,3,2]

Final result[1, 2, 3]

C · Code with teaching comments

solution.javaJava

Shift-and-insert — optimal

2 teaching notes

1
public void insertionSort(int[] nums) {
2
    for (int i = 1; i < nums.length; i++) {
3
        int key = nums[i];
4
        int j = i - 1;
5
        while (j >= 0 && nums[j] > key) {
6
            nums[j + 1] = nums[j];
7
            j--;
8
        }
9
        // Drop the key into its correct position.
10
        nums[j + 1] = key;
11
    }
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — worst case shifts the whole prefix each time → O(n²); on nearly-sorted data few shifts → O(n).

E · Edge cases and pitfalls5nums = [1, 2, 3] — Already sorted → O(n), no shifts.Explore edge cases

Edge cases handled

nums = [1, 2, 3]Already sorted → O(n), no shifts.
nums = [2, 1]One insert → [1, 2].
nums = [3, 2, 1]Reverse → worst-case O(n²).

Pitfalls

Overwriting the key before shifting (save it first).
Off-by-one when placing the key (j+1).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void insertionSort(int[] nums) { for (int i = 1; i < nums.length; i++) { int key = nums[i]; int j = i - 1; while (j >= 0 && nums[j] > key) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Overwriting the key before shifting (save it first).
Off-by-one when placing the key (j+1).

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Shift-and-insert

Code pattern to memorize

for i: key=a[i]; shift a[j]>key right; a[j+1]=key

Rules to remember

1Sorted prefix grows.
2Shift larger elements right.
3Fast on nearly-sorted data.

Use this pattern when

Nearly-sorted data
Base case of hybrid sorts

Interview takeaway

Insertion sort shines when the data is almost sorted.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Shift-and-insert. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Bubble Sort
Another O(n²) stable sort with early exit.

Same pattern