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

Top-Down Merge Sort

Split recursively to single values, then merge sorted halves while the call stack exposes divide and conquer.

Core idea

Recursively split an interval until each leaf contains one value. On the return path, merge two sorted halves into an auxiliary buffer and copy the result back.

Read the visualization

The interval stack shows the active recursive frame. During a merge, two read pointers choose the next value, an auxiliary pointer fills the buffer, and write-back restores the source interval.

6
3
8
1
9
2
7
4
Interval stack: each frame is a pending subarray a[lo..hi]
a[0..7]

Split the current interval into two smaller recursive problems.

1function mergeSort(a: number[], lo = 0, hi = a.length - 1): number[] {
2 if (lo >= hi) return a;
3 const mid = (lo + hi) >> 1;
4 mergeSort(a, lo, mid);
5 mergeSort(a, mid + 1, hi);
6 const temp: number[] = [];
7 let i = lo, j = mid + 1;
8 while (i <= mid && j <= hi) {
9 if (a[i] <= a[j]) {
10 temp.push(a[i++]);
11 } else {
12 temp.push(a[j++]);
13 }
14 }
15 while (i <= mid) temp.push(a[i++]);
16 while (j <= hi) temp.push(a[j++]);
17 for (let k = 0; k < temp.length; k++) a[lo + k] = temp[k];
18 return a;
19}
n8
depth1
lo0
mid3
hi7
i-
j-
k-
a[i]-
a[j]-
writeCount0
1 / 63

Complexity and tradeoffs

Time: O(n log n). Space: O(n). Stable with predictable work; recursion adds O(log n) stack frames beside the merge buffer.

Invariant: Every recursive call returns with its interval sorted and containing exactly the values it received.

Where it fits

Top-down Merge Sort gives stable, predictable performance and adapts naturally to linked lists and external sorting. Arrays pay for an auxiliary buffer and recursive frames.