Binary Sort Simulation
Binary Sort (Binary Insertion Sort) uses binary search on the sorted left subarray to locate where each key belongs in O(log n) comparisons, then shifts elements right to insert it.
Interactive simulation
- Key
- -
- Search [L..H]
- -
- Mid
- -
- Sorted prefix
- 1 / 10
- Speed
- 1x
Ready: press Insert Next or Resume to start
Legend
- Sorted prefix
- Binary search range [low..high]
- Mid probe / active key (lifted)
- Shifting right (lifted)
Event log
How to use this simulation
- Press Insert Next once to advance through one binary probe, shift, or insertion event, or press Resume to animate continuously.
- Watch selected/active bars lift upward and slide across slots as binary search narrows the range and elements shift right.
- Use Step, Slower (down to 0.25x), Faster (up to 4x), and Reset to test new values.
1. Binary search on the sorted prefix
Because elements 0 .. i - 1 are already sorted, Binary Sort halves the search interval [low, high] using mid = Math.floor((low + high) / 2) to find the exact insertion index.
2. Shifting & inserting the key
Once low pinpoints the target slot, elements from i - 1 down to low shift one index right so key is written into arr[low].
3. Comparisons vs. shifts
Comparisons drop to O(n log n) overall, but shifting elements still takes up to O(n²) shifts in the worst case and O(1) auxiliary space.