bisect: hi < lo Silently Corrupts insort's Sort Order (tested)

bisect's lo/hi parameters let you search or insert into a slice of a list instead of the whole thing. A negative lo is rejected immediately. But if a computed hi ends up smaller than lo -- an off-by-one in whatever expression produced it -- nothing stops the call. We measured exactly what happens.

1. Negative lo raises -- but hi < lo doesn't

import bisect

a = [1, 3, 5, 7, 9]

try:
    bisect.bisect_left(a, 4, -2)
except ValueError as e:
    print("lo=-2 error:", e)

print("hi<lo, no error:", bisect.bisect_left(a, 4, 3, 1))

lo=-2 error: lo must be non-negative
hi<lo, no error: 3

Measured: bisect explicitly checks for a negative lo and raises ValueError. It performs no equivalent check that hi >= lo. Internally the search loop is while lo < hi, so when hi is already less than lo the loop never runs and the function just returns lo unconditionally -- not an error, not necessarily the index you'd want, just whatever lo happens to be.

2. insort with hi < lo inserts into the wrong place -- with no warning

import bisect

c = [1, 3, 5, 7, 9]
bisect.insort_right(c, 100, 3, 1)  # hi=1 < lo=3, by mistake
print(c)

[1, 3, 5, 100, 7, 9]

Measured: 100 is larger than every element in the list, so a correct insert would put it at the end. Instead it lands at index 3 -- the middle of the list -- because insort_right calls the same unguarded bisect_right(a, x, lo, hi) internally and gets back lo with no error. The result, [1, 3, 5, 100, 7, 9], is no longer sorted, and nothing in the call raised, warned, or returned a sentinel to say so.

3. This happens with ordinary, not adversarial, inputs

import bisect

def insert_recent(buffer, value, window_start_idx):
    # bug: hi should be len(buffer), not window_start_idx - 1
    bisect.insort_right(buffer, value, window_start_idx, window_start_idx - 1)

buf = [10, 20, 30, 40, 50]
insert_recent(buf, 999, 2)
print(buf)

[10, 20, 999, 30, 40, 50]

Measured: a plausible off-by-one -- passing window_start_idx - 1 as hi instead of the list length -- produces hi=1 < lo=2. 999 silently lands at index 2 instead of the end, and the list is now unsorted. The bug surfaces later, wherever something assumes buf stays sorted (another bisect call, a binary search, a "top-N" slice) -- far from where the bad hi was actually computed.

Validate hi >= lo yourself if you compute either one

import bisect

def safe_insort_right(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    if hi < lo:
        raise ValueError(f"hi ({hi}) must be >= lo ({lo})")
    bisect.insort_right(a, x, lo, hi)

If lo and hi are both fixed literals (the common case: searching/inserting into the whole list), this never comes up. It only bites when one or both are computed -- a cached length, a loop index, a window boundary -- and that computation can go stale or off-by-one relative to the other.

Written with AI assistance. Measured on 2026-10-08 with Python 3.13.5's built-in bisect module: called bisect_left/bisect_right/insort_right with a negative lo (which raises) versus hi < lo (which doesn't raise, and silently breaks the sort invariant). PlainHeaders is our extension; Python's bisect module is built in.