Insertion Sort
An easy Sorting interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sorting
- Sheets
- 2
- Core for
- 13 roles
The problem
Sort an array by building a sorted portion one element at a time, inserting each new element into its correct position within the sorted part.
Example 1
- Input
- nums = [12, 11, 13, 5, 6]
- Output
- [5, 6, 11, 12, 13]
Example 2
- Input
- nums = [6, 5, 3, 1, 8, 7, 2, 4]
- Output
- [1, 2, 3, 4, 5, 6, 7, 8]
Constraints
- 1 <= nums.length <= 100
- -10^4 <= nums[i] <= 10^4
How to think about it
Updated 2026-09-29Treat the array as an expanding sorted deck in your left hand. Each newcomer arrives at the edge of the sorted prefix; shifting larger predecessors rightward by one step opens up precisely one vacant slot where the candidate belongs, leaving the enlarged prefix completely sorted at every stage.
Approaches, worst first
Adjacent swap insertion
time O(n^2) · space O(1)
Bubble the newcomer backward one swap at a time until it meets an element smaller than itself. Short to write, but each swap does three assignments where a single temporary save and a sequence of shifts suffices.
Shift and dropWrite this one
time O(n^2) · space O(1)
Cache the current element in a variable, shift every strictly larger element one index to the right, and drop the cached value into the opening. On already or nearly sorted inputs, each element tests its immediate left neighbor and stops.
Where people lose marks · 3
- Overwriting the candidate element before caching it in a temporary variable: the first rightward shift clobbers nums[i] if it has not been saved.
- Off-by-one underflow when walking the pointer j leftward; checking `j >= 0` must precede accessing `nums[j]` to avoid reading past index 0.
- Using `<=` instead of `<` when checking if predecessors are larger swaps identical keys past one another, discarding the natural stability of the algorithm.
The theory behind it
Sorting — the ground this problem stands on. All Sorting problems
What Sorting is
Sorting is the act of arranging a scrambled hand of playing cards into ascending rank from left to right. It reorganizes scattered data according to a consistent comparison rule, like numbering index cards or alphabetizing names. While unsorted data requires searching every single entry to verify whether an item exists, ordered data establishes predictable relationships that make duplicates, clusters, and extreme values immediately visible.
When to reach for it
Reach for sorting when a problem asks to group identical items, detect overlaps among intervals, find rank percentiles, or pair values matching a target sum. If an unordered problem appears intractable in polynomial time, sorting the input frequently unlocks linear scans or two-pointer sweeps. When an O(n log n) preprocessing step simplifies downstream matching logic, sorting is usually the right opening move.
How the pattern works
Think of sorting as a trade: invest logarithmic overhead upfront to make subsequent queries direct and orderly. Compare adjacent elements to uncover duplicate entries, or march inward from outer boundaries once elements stand in monotonic sequence. When designing custom comparators, confirm strict weak ordering by verifying reflexivity, antisymmetry, and transitivity; inconsistent comparison logic breaks internal pivot partitions or produces corrupted outputs.
More Sorting problems
Target Roles
Core requirement for 13 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .