Interactive demo
Block Sort Visualization
Block sort, or block merge sort, is a stable merge sort that needs no extra memory. To merge two sorted parts A and B, it splits A into blocks, rolls them through B with block swaps and drops each block where it belongs.
Watch the last merge: the violet A blocks roll through the amber B values and are dropped one after the other.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Element
- Part A (blocks)
- Part B
- Moved block or values
- Final position
Runtime and properties
Best case
O(n)
Already sorted parts are recognized with a single comparison per merge.
Average case
O(n log n)
Merging with √n blocks costs O(n) per level, over log n levels.
Worst case
O(n log n)
The block sizes never depend on the values, so every merge stays O(n).
Extra memory
O(1)
Only a few indexes; the original even keeps its buffers inside the array.
Stable
Yes
Blocks keep their original order, and local merges never pass equal elements.
In-place
Yes
Everything happens through block swaps and rotations within the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort this page | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Small groups, then merging
First, small groups are sorted with insertion sort. Then neighboring parts are merged bottom-up, like merge sort, but without an auxiliary array.
2. Rolling and dropping
A is split into blocks of about √|A| elements. The next B block swaps places with the first A block, so the A blocks roll through B. As soon as the smallest A block belongs among the B values it just passed, it is dropped there by a rotation.
3. Simplified here
This visualization keeps the order of the A blocks in a small list and always merges locally with rotations. The original stores this order in the array itself, using a buffer of unique values, and uses a second buffer to merge faster.
Credits
- This visualization follows WikiSort by BonzaiThePenguin, which implements “Ratio based stable in-place merging” by Pok-Son Kim and Arne Kutzner, simplified as described above.