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

    1. Press Insert Next once to advance through one binary probe, shift, or insertion event, or press Resume to animate continuously.
    2. Watch selected/active bars lift upward and slide across slots as binary search narrows the range and elements shift right.
    3. 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.

    Related topics