SortVivo - Sort Algorithm Visualization

Block sort (WikiSort)(2008)

O(n log n) ✓ Stable ✓ In-place

🔧 How it works

A stable in-place merge sort that operates bottom-up in three stages: sorting-network seeds for tiny groups, cache-based merges for small levels, and block-based merges for large levels using internal buffers borrowed from the array itself. Falls back to rotation merging when internal buffers cannot be extracted.

🎯 Key property

Instead of allocating a full-size merge buffer, the algorithm borrows a region of unique values from inside the array as scratch, then returns it afterward, achieving O(1) auxiliary space while preserving stability and O(n log n) time.

👁 Watch for

Compare binary searches (lower-bound and upper-bound) locate merge points and A-block roll positions; the bound pair keeps equal elements from the left run ahead of those from the right
Swap buffer extraction, block rolling, and buffer redistribution all use swap sequences; at the large-level phase, Swap is the dominant operation
RangeCopy the fixed 512-element cache, rented from a shared pool, serves small-level merges directly; at large levels, cache merges each dropped A-block with trailing B values when both fit

🕰 History 🌳 Lineage ⚡ Optimization

Initial State

This is the array before sorting. Follow Block sort (WikiSort) step by step.

Recursion Tree

0 / 627 ops ( 0.0%) 0.0%