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

Binary Insertion Sort

Use binary search inside the sorted prefix to locate an insertion point before shifting values into place.

Core idea

Binary search locates the stable insertion boundary inside the sorted prefix. The array then shifts the suffix of that prefix and places the key at the boundary.

Read the visualization

First watch the half-open search interval shrink around the insertion point. The second phase highlights every value moved right before the key enters the gap.

5
2
9
4
7
1
8
3

Take the next key and search for its position inside the sorted prefix.

1function binaryInsertionSort(a: number[]): number[] {
2 for (let i = 1; i < a.length; i++) {
3 const key = a[i];
4 let lo = 0, hi = i;
5 while (lo < hi) {
6 const mid = (lo + hi) >> 1;
7 if (key < a[mid]) {
8 hi = mid;
9 } else {
10 lo = mid + 1;
11 }
12 }
13 const pos = lo;
14 for (let k = i; k > pos; k--) {
15 a[k] = a[k - 1];
16 }
17 a[pos] = key;
18 }
19 return a;
20}
n8
i1
key2
lo-
mid-
hi-
pos-
shiftCount0
sortedUpTo1
1 / 67

Complexity and tradeoffs

Time: O(n log n) comparisons; O(n^2) moves. Space: O(1). Binary search reduces comparisons, but contiguous insertion still requires shifting the suffix.

Invariant: The binary-search boundary is the first prefix position greater than the key, so inserting there preserves both order and stability.

Where it fits

This variant helps when comparisons are costly, but it cannot avoid the quadratic number of array moves. Linked storage changes the move cost but loses direct midpoint access.