V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Insertion Sort

Grow a sorted prefix by shifting larger values right and inserting each key into its final local position.

Core idea

Treat the left prefix as sorted. Remove the next key, shift every larger prefix value one step right, and insert the key into the resulting gap.

Read the visualization

The key marker stays attached to the value being inserted. Comparisons move left through the prefix, and each shift visibly opens the gap that eventually receives the key.

7
6
5
10
9
8
4
3
2
1

Remove the next key from the unsorted suffix and open a position in the sorted prefix.

1function insertionSort(a: number[]): number[] {
2 const n = a.length;
3 for (let i = 1; i < n; i++) {
4 const key = a[i];
5 let j = i - 1;
6 while (j >= 0 && a[j] > key) {
7 a[j + 1] = a[j];
8 j--;
9 }
10 a[j + 1] = key;
11 }
12 return a;
13}
n10
i1
key6
j0
a[j]7
shiftCount0
sortedUpTo1
1 / 94

Complexity and tradeoffs

Time: Average/worst O(n^2); best O(n). Space: O(1). Stable, adaptive, and effective for small or nearly sorted inputs.

Invariant: At the start and end of every outer iteration, the processed prefix is sorted and contains exactly its original values.

Where it fits

Insertion Sort is a strong base case for hybrid sorts and performs well on small or nearly sorted arrays. Stable insertion also makes it useful inside more specialized algorithms.